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$
3
  • $\begingroup$ Your definition of $N(I)$ is neither necessary nor correct. $\endgroup$
    – Yixin Cao
    Nov 20, 2014 at 14:01
  • 2
    $\begingroup$ Could you please explain why? $\endgroup$
    – mort
    Nov 20, 2014 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, 2014 at 14:09

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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