# Crown Rule Reduction In Parameterized Complexity - Vertex Cover - Notion Question

I am reading the paper "Kernelizations for Parameterized Counting Problems", and had a question regarding some of the notation in the paper (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.8295&rep=rep1&type=pdf).

In section 4, the author begins by defining the notion of a crown as follows:

Let $\mathcal{G} := (V, E)$ be a graph. A crown in $\mathcal{G}$ is a bipartite subgraph $\mathcal{C} = (I, N(I), F)$ of $\mathcal{G}$ satisfying the following three conditions.

• $I$ is an independent set in $\mathcal{G}$ and $N(I)$ is the set of all neighbours of vertices from $I$ in $\mathcal{G}$.
• $F$ contains all of the edges of $E$ that connect vertices from $I$ to $N(I)$.
• $\mathcal{C}$ has a matching of cardinality $|N(I)|$.

In then goes on to define a few other pieces of notation. Let $\mathcal{G} - \mathcal{C}$ be the graph obtained from $\mathcal{G}$ by deleting all of the vertices in $\mathcal{C}$ and all edges incident to vertices in $\mathcal{C}$. Also, let $S_\mathcal{C}$ be a vertex cover of $\mathcal{C}$ and let $\mathcal{G}' := (V', E')$ be the graph obtained from $\mathcal{G} - \mathcal{C}$ by deleting all edges covered by vertices in $S_\mathcal{C}$.

What confuses me here is the difference between $\mathcal{G} - \mathcal{C}$ and $\mathcal{G}'$. Since the vertex cover contains only vertices in $I$ or $N(I)$, when removing $\mathcal{C}$ from $\mathcal{G}$, haven't we already removed all of the edges that can be covered by vertices in $S_\mathcal{C}$? It would seem to me that the edges in $\mathcal{G} - \mathcal{C}$ do not have any vertices that are incident, making it identical to $\mathcal{G}'$. Where is the error in my reasoning/understanding?

Thanks!!

• From your description, I don't see any errors. – caozhu Feb 20 '14 at 9:04
• But then, $\mathcal{G}'$ would always be the same graph as $\mathcal{G} - \mathcal{C}$, making it pointless to define one right after the other in the paper. The way I have described it (or at least to my understanding), we will never remove any edges to obtain $\mathcal{G}'$... which is what I find strange, since the two are defined consecutively in the paper. – Nizbel99 Feb 20 '14 at 9:50

I agree with the OP: $\mathcal{G} - \mathcal{C} = \mathcal{G}'$.
I assume the author of the paper wanted to define $\mathcal{G}'$ as $\mathcal{G} - S_{\mathcal{C}}$. With this modification, the next sentence in the paper makes sense:
One can easily see that $\#vc(\mathcal{G}',k-|S_{\mathcal{C}}|)$ equals the number of size $k$ vertex covers $S$ in $\mathcal{G}$ with $S \supseteq S_{\mathcal{C}}$.
Here, $\#vc(\mathcal{G},k)$ denotes the number of size $k$ vertex covers in $\mathcal{G}$.
• Actually, I do have another concern. If $\mathcal{G}' \neq \mathcal{G} - \mathcal{C}$, but rather equal to $\mathcal{G} - S_\mathcal{C}$, how is it that $V' \leq 3k$ (right after your quote) when they also state that $\mathcal{C}$ has at least $V - 3k$ vertices (condition C). Doesn't that cause an issue? (Sorry, I have been staring at this for so long that I am confusing myself). Can't $\mathcal{G} - S_\mathcal{C}$ contain vertices from $N(I)$ if they are not part of the vertex cover? – Nizbel99 Feb 26 '14 at 1:14
• Yes, $\mathcal{G}-S_{\mathcal{C}}$ can contain vertices from $N(I)$. We know that $|N(I)|\le k$, otherwise there is no vertex cover of size at most $k$, since a vertex cover must contain at least one vertex for every edge in a matching. So, one can trivially get $|V'|\le 4k$, which does not compromise the result. If you insist on obtaining $|V'|\le 3k$ you could get $\mathcal{C}$ with at least $|V|-2k$ vertices by computing a crown decomposition using the Nemhauser-Trotter theorem (1975, dx.doi.org/10.1007/BF01580444). – Serge Gaspers Feb 26 '14 at 3:22
• Ah - I do see the $4k$ bound, but given that the paper states that their crown contains at most $|V| - 3k$ vertices and that I don't see that theorem cited anywhere, I think it could of been a typo. I will just use the $4k$ bound for my presentation ... makes things much easier to explain. – Nizbel99 Feb 26 '14 at 3:38