1

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?

jarrad_obrien
  • 391
  • 1
  • 4
  • 15
  • 1
    Is the heuristic part of the question or is it your own suggestion as a heuristic to the question "Show that there EXISTS a heuristic..." ? – shole Oct 25 '16 at 03:46
  • It's given as part of the question, it's not one that I made up. – jarrad_obrien Oct 25 '16 at 03:50
  • Vertex cover is covering the *edges*. You need one of the endpoints of each edge. You seem to be thinking of a different problem. – user2357112 Oct 25 '16 at 04:09
  • You're right, I got it confused with a minimal spanning tree. I'll edit the question. I'm still not sure how to show that the heuristic is at most twice as large however. – jarrad_obrien Oct 25 '16 at 04:47
  • It's not a factor-2 optimization for MST. – Ami Tavory Oct 25 '16 at 05:32
  • interesting problem..a several words appear in my mind but I do not know if they are the keys to the problem: DFS tree, vertex cover on tree (greedy algorithm), and you must choose one endpoints out of TWO ends of an edge... – shole Oct 25 '16 at 06:36

2 Answers2

0

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

Alexander Anikin
  • 1,108
  • 6
  • 14
0

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.

kraskevich
  • 18,368
  • 4
  • 33
  • 45