Show that the heuristic solution to vertex cover is at most twice as large as the optimal solution

Question

The heuristic solution that I've been given is:

• Perform a depth-first-search on the graph
• Delete all the leaves
• The remaining graph forms a vertex cover

I've been given the question: "Show that this heuristic is at most twice as large as the optimal solution to the vertex cover". How can I show this?

Answer 1

I assume that the graph is connected (if it's not the case, we can solve this problem for each component separately).

I also assume that a dfs-tree is rooted and a leaf is a vertex that doesn't have children in the rooted dfs-tree (it's important. If we define it differently, the algorithm may not work).

We need to show to things:

1. The set of vertices returned by the algorithm is a vertex cover. Indeed, there can be only types of edges in the dfs-tree of any undirected graph: tree edges (such an edge is covered as at least on of its endpoints is not a leaf) and a back edge (again, one of its endpoint is not a leaf because back edge goes from a vertex to its ancestor. A leaf cannot be an ancestor of a leaf).

2. Let's consider the dfs-tree and ignore the rest of the edges. I'll show that it's not possible to cover tree edges using less than half non-leave vertices. Let S be a minimum vertex cover. Consider a vertex v, such that v is not a leaf and v is not in S (that is, v is returned by the heuristic in question but it's not in the optimal answer). v is not a leaf, thus there is an edge v -> u in the dfs-tree (where u is a successor of v). The edge v -> u is covered by S. Thus, u is in S. Let's define a mapping f from vertices returned by the heuristic that are not in S as f(v) = u (where v and u have the same meaning as in the previous sentence). Note that v is a parent of u in the dfs-tree. But there can be only one parent for any vertex in a tree! Thus, f is an injection. It means that the number of vertices in the set returned by the heuristic but not in the optimal answer is not greater than the size of the optimal answer. That's exactly what we needed to show.

Answer 2

Bad news: heuristics does not work. Strictly said, 1 isolated vertex is counter-example for the question. Nevertheless, heuristic does not provide vertex cover solution at all, even if you correct it for isolated vertex and for 2-point cliques. Take a look at fully connected graphs with number of vertexes from 1 to 3:

1 - strictly said, isolated vertex is not a leaf (it has degree 0, while leaf is a vertex with degree 1), so heuristic will keep it, while vertex cover will not

2 - heuristic will drop both leaves, while vertex cover will keep at least 1 of them

3 - heuristic will leave 1 vertex, while vertex cover has to keep at least 2 vertexes of this clique