0
$\begingroup$

I'm currently reading "Invitation to Fixed-Parameter Algorithms" by Rolf Niedermayer. Page 69 gives the following definition of the crown of a graph, which I do not quite understand:

A crown of a graph $G = (V,E)$ consists of $H\subseteq V$ and $I \subseteq V$ with $H \cap I = \varnothing$ s.t. the following three conditions hold:

  • $H = N(I)$
  • $I$ forms an independent set
  • the edges connecting $H$ and $I$ contain a matching in which all elements of $H$ are matched.

$N(I)$ is the neighborhood of vertices $I$, i.e., $N(I) = \{u \mid v \in I \land (u,v) \in E\}$.

I'm stuck with the third point: I'm interpreting it as "in the bipartite graph $(H, I, F)$ with $F = \{(u,v) \in E \mid u\in I \land v \in H\}$ there is a matching $M\subseteq F$ s.t. $\forall v \in H: \exists (u,v) \in F$, i.e., each vertex in $H$ is covered by an edge in the matching $M$".

But does this not imply that $|I| \geq |H|$ since there can at most be $|I|$ non-adjacent edges connected to vertices in $I$? This would imply that $I$ is a set of vertices that have degree 1, which surely is not the intention since a crown is intended to be a generalization of 1-connected vertices.

What am I missing?

$\endgroup$
  • $\begingroup$ Your definition of $N(I)$ is neither necessary nor correct. $\endgroup$ – Yixin Cao Nov 20 '14 at 14:01
  • 1
    $\begingroup$ Could you please explain why? $\endgroup$ – mort Nov 20 '14 at 14:04
  • $\begingroup$ $H$ is supposed to be a generalization of the cutpoint (a 1-connected vertex?), not $I$. $\endgroup$ – Yixin Cao Nov 20 '14 at 14:09
2
$\begingroup$

Yes, it implies that $|I| \geq |H|$ but it does not imply $I$ contains only vertices of degree 1. The edges joining $H$ to $I$ contain an H-covering matching, but there can be many more edges. See, for instance, D. Marx' slides on crown reduction: http://www.cs.bme.hu/~dmarx/papers/marx-agape09-slides-print.pdf

$\endgroup$

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.