3
$\begingroup$

Question taken from "The Algorithm Design Manual" by Steven S. Skiena, 1997.

A vertex cover of a graph $G=(V,E)$ is a subset of vertices $V'\subseteq V$ such that every edge $e\in E$ contains at least one vertex from $V′$.

Delete all the leaves from any depth-first search tree of $G$. Must the remaining vertices form a vertex cover of $G$? Give a proof or a counterexample.

Answer given :

If the tree has more than one vertex, then yes. The remaining vertices are still the vertex cover because for every edge e∈E incident on the leaves, their other end-point is still in the remaining tree.

My question:

The answer is right for undirected graphs. But I think there exist counterexamples to this question using directed graphs.

For example:

counterexample using a directed graph

If we are using DFS starting from vertex $a$ and we are traversing in alphabetical order, i.e. explore b first, then we end up with two tree edges, which are $(a,b)$ and $(a,c)$. Therefore, $b$ and $c$ are leaf-vertices.

But here if are going to delete vertices $b$ and $c$ the edge $(c,b)$ has no incident vertices which are contained in our vertex cover.

Am I right? I am confused actually.

$\endgroup$
  • $\begingroup$ I believe the question and the book are strictly talking about undirected graphs. $\endgroup$ – Juho Jul 11 '16 at 17:32
  • $\begingroup$ @Juho As it was not specified explicitly so I thought of directed case $\endgroup$ – ViX28 Jul 11 '16 at 17:39
  • 4
    $\begingroup$ If you want to consider directed graphs, you will have to define what a vertex cover is (on a directed graph). $\endgroup$ – Juho Jul 11 '16 at 17:51
4
$\begingroup$

Look at the definition of vertex cover (as provided by the book). It is strictly defined on undirected graphs. Thus, the answer doesn't apply to directed graphs, nor to any other kinds of graphs you might think of. So your counterexample is invalid, as it makes invalid assumptions (graphs are always undirected here). These invalid assumptions are the source of your confusion.

To consider directed graphs, we first need to define what a vertex cover is on a directed graph. Well, we can say it is a subset of vertices such that every arc is incident to at least one vertex in the subset. Again, the book makes no claim about such directed vertex covers. If you are now asking "does $\{ a \}$ form a (directed) vertex cover as per our definition?", the answer is NO as you correctly observed.

$\endgroup$

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.