1
$\begingroup$

I'm trying to understand a poly-time reduction proof from dominating set to vertex cover. If I'm understanding correctly, it goes something like this: suppose we have a vertex cover of size $k$ in graph $G$. Then we construct a new graph $G^\prime$ with the same vertices and edges, except for every edge $(u,v)$ we add a new vertex $w_{uv}$, which has an edge to both $u$ and $v$.

Then, here's the oddest part: it says that if there's some dominating set in $G^\prime$ that includes any of the $w_{uv}$, then we can construct another dominating set, that's at least as good, by replacing that $w_{uv}$ with either $u$ or $v$. That is, we end up not including any of the $w_{uv}$ at all, and thus the dominating set in $G^\prime$ is the vertex cover in $G$ plus any remaining isolated vertices not in the cover.

This raises the obvious question: what's the point of $w_{uv}$ if we're gonna include them and then argue that the original $u$ and $v$ can render them obsolete anyway? The proof in the link above conspicuously does not explain this. If the dominating set of $G^\prime$ doesn't even include $w_{uv}$, and the vertex cover dominates just fine (except for the isolated vertices, which are trivial and have nothing to do with $w_{uv}$), why even add the $w_{uv}$? Why does the proof fail if we never introduce the $w_{uv}$ at all?

$\endgroup$

1 Answer 1

1
$\begingroup$

The key reason we need $w_{uv}$ is because not every dominating set is necessarily a vertex cover, but $w_{uv}$ "patches" that up.

In particular, assume isolated vertices can be ignored. Then every vertex cover is a dominating set, but not every dominating set is a vertex cover. Hence, if we tried to do the reduction without adding $w_{uv}$, then only one direction would work: we can show that if $G$ has a vertex cover of size $k$, then $G$ also has a dominating set of the same size. However, the converse is not true; only by adding the $w_{uv}$ does every dominating set of $G^\prime$ necessarily dominate the $w_{uv}$ as well, and thus cover all edges in $G$.

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