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$


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.


In the book Kernelization by Fomin, Lokshtanov, Saurabh, Zehavi (which is downloadable as a PDF on the first author's homepage) you find Chapter 4. Crown decomposition. This should point you to the answer.

  • $\begingroup$ I didnt find the answer. I searched that chapter $\endgroup$
    – Sid
    May 7 at 4:10
  • $\begingroup$ Please specify the page number $\endgroup$
    – Sid
    May 7 at 4:10
  • 1
    $\begingroup$ Where in the algorithm are you stuck? $\endgroup$
    – Pål GD
    May 7 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.