[Solved]: Vertex cover of a graph by removing leaf-vertices from a DFS tree

Problem Detail: 

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:

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.

Asked By : ViX28

Answered By : Juho

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60509

3.2K people like this

 Download Related Notes/Documents