4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ From your description, I don't see any errors. $\endgroup$ – caozhu Feb 20 '14 at 9:04
  • $\begingroup$ 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. $\endgroup$ – Nizbel99 Feb 20 '14 at 9:50
2
+100
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I agree - That would seem to be the case. Thanks for confirming my suspicion. $\endgroup$ – Nizbel99 Feb 24 '14 at 22:23
  • $\begingroup$ 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? $\endgroup$ – Nizbel99 Feb 26 '14 at 1:14
  • 1
    $\begingroup$ 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). $\endgroup$ – Serge Gaspers Feb 26 '14 at 3:22
  • $\begingroup$ 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. $\endgroup$ – Nizbel99 Feb 26 '14 at 3:38

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.