<p>I agree with the OP: $\mathcal{G} - \mathcal{C} = \mathcal{G}'$.</p>

<p>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:</p>

<blockquote>
  <p>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}}$.</p>
</blockquote>

<p>Here, $\#vc(\mathcal{G},k)$ denotes the number of size $k$ vertex covers in $\mathcal{G}$.</p>

CC BY-SA 3.0
2014-02-24T22:23:30.950Z
I agree - That would seem to be the case. Thanks for confirming my suspicion.
Nizbel99
CC BY-SA 3.0
2014-02-26T01:14:09.507Z
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
CC BY-SA 3.0
2014-02-26T03:22:10.357Z
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, http://dx.doi.org/10.1007/BF01580444).
Serge Gaspers
CC BY-SA 3.0
2014-02-26T03:38:30.817Z
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
CC BY-SA 3.0
2014-02-23T07:36:02.987Z
2014-02-23T07:36:02.987Z
Serge Gaspers
<p>I am reading the paper "Kernelizations for Parameterized Counting Problems", and had a question regarding some of the notation in the paper (<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.8295&amp;rep=rep1&amp;type=pdf" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.8295&amp;rep=rep1&amp;type=pdf</a>).</p>

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

<p>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.</p>

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

<p>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}$.</p>

<p>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?</p>

<p>Thanks!!</p>

CC BY-SA 3.0
2014-02-20T09:04:54.007Z
From your description, I don't see any errors.
caozhu
CC BY-SA 3.0
2014-02-20T09:50:11.967Z
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
<graph-algorithms><parameterized-complexity>
Crown Rule Reduction In Parameterized Complexity - Vertex Cover - Notion Question
Nizbel99
# Crown Rule Reduction In Parameterized Complexity - Vertex Cover - Notion Question

(Asked by: username_0 on 2014-02-20)

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!!

**Tags:** graph-algorithms, parameterized-complexity

> **Comments:**
> **username_1**: From your description, I don't see any errors.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2014-02-23. Score: 2 | Accepted answer

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}$.

> **Comments:**
> **username_0**: I agree - That would seem to be the case. Thanks for confirming my suspicion.  
> **username_0**: 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?  
> **username_2**: 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, http://dx.doi.org/10.1007/BF01580444).  
> **username_0**: 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.  

---

