patternMinor
Vertex cover of a graph by removing leaf-vertices from a DFS tree
Viewed 0 times
fromgraphremovingvertexdfsleafcoververticestree
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#60509, answer score: 5
Revisions (0)
No revisions yet.