# algorithms – Constructing a crown graph given an independent set

A crown in a graph G is a pair (H, C), where H ⊆ V(G) and C ⊆ 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.

Posted on