# Constructing a crown graph given an independent set

A crown in a graph $$G$$ is a pair $$(H, C)$$, where $$H \subseteq V(G)$$ and $$C \subseteq V(G)$$ with $$H ∩ C = ∅$$ such that the following conditions hold:

(a) The set of neighbors of vertices in $$C$$ is precisely $$H$$, i.e. $$H = N(C)$$,

(b) $$C = C_m \cup C_u$$ is an independent set, and

(c) There is a perfect matching between $$C_m$$ and $$H$$

Theorem:

Any graph $$G(V,E)$$ with an independent set $$I$$, where $$|I| ≥ \dfrac{2n}{3}$$ , has a crown $$(H, C)$$, where $$H ⊆ N(I), C ⊆ I$$ and $$C_u \ne ∅$$, that can be found in time $$O(nm)$$ given $$I$$. $$(n=|V|, m = |E|)$$

I am trying to code an algorithm to find such a crown in $$O(nm)$$ time

The only way I could think of finding a crown given an independent set is to take subsets of the set: $$I$$ and check for all the three conditions of a crown. However, taking all subsets of $$I$$ will take exponential time right? How to find it in $$O(nm)$$ time. I just want an algorithm with polynomial time. It need not be $$O(nm)$$... It can be in the form $$O(n^c m^d)$$ where $$c,d$$ are constants.

• sciencedirect.com/science/article/pii/S0304397509002837
– Sid
May 6 at 17:21
• This paper cites this paper: researchgate.net/publication/…. Furthermore, this paper cites [CFJ03, page 7], and [F03, page 8]. Did you try to work out the proof based on these two references. May 6 at 17:34
• I looked through it. I can't seem to prove the theorem or come up with an algorithm the definetly constructs a crown if it exists.
– Sid
May 6 at 17:35
• – D.W.
May 6 at 18:30
• I encourage you to revise the question based on the feedback you received here and on Stack Overflow to provide background on everything you know about this paper and summarize, so people don't have to read the comments to get this information.
– D.W.
May 6 at 18:31