Monday, March 5, 2012

Find the Minimun Vertex Cover for a Tree

Problem: Given a tree, find its minimum vertex cover. Wait, what is a vertex cover? Given a undirected graph G(V,E),  a vertex cover is a subset of V such that for any egde e in E, at least one of e's two endpoints should be in this subset (vertex cover).

Solution: The minimum vertex cover for a general graph is a NP-hard problem. However, for a tree, there is a linear solution. The idea here is to do DFS search plus post-order traversal. If we encounter a leaf node and the edge connecting this leaf node with its parent, we know in order to construct a vertex cover, we must include at least one of the node (the leaf node, or its parent). Here we can use a greedy approach. We can see selecting the leaf doesn't give us any extra benefit, while selecting the parent can give us some benefit, since the parent must be also connected to other nodes. By selecting the parent node, we can further "cover" some extra edges. With this strategy in mind, our algorithm is as follow:

  • we do a DFS search. When a DFS call on a child node returns, we check if the child and the parent are both unselected. If yes, we select the parent node.
  • After all the DFS finishes (we traverse the tree), those selected nodes form the minimum vertex cover. The cost is O(N).
The pseudo code is as follow:
void min_vertex_cover(TreeNode *root)
{
   if(isLeaf(root)) return; 

   for(int i=0; i<root->num_of_children; i++)
   { 
        min_vertex_cover(root->children[i]);

        if(!root->selected && !root->children[i]->selected)
               root->selected = true;
         
   }
}

6 comments:

  1. It's worth adding that we shouldn't start from a leaf. Thus, your algorithm doesn't work for a tree with one edge.

    ReplyDelete
  2. Moreover, you have to check if child has never been checked before to avoid loops.
    You adding that for people who implemented the algorithm and got SIGSEGV.

    ReplyDelete
  3. I think you logic fails in case of skewed tree. Consider a skewed tree with 6 nodes with following connectivity:

    1,2; 2,3; 3,4; 4,5; 5,6. So, applying your algorithm will get us {1,3,5} as vertex cover set, but the correct answer will be {2,5}.

    ReplyDelete
    Replies
    1. The set {2,5} is not a vertex set. The edge 3,4 does not have any end points in the set.

      Delete
  4. The right solution would be to always choose either a node or its parent and propagate both the solutions to the parent node of that node. Then subsequent calls can decide which solution to pick, so there will always be 2 solutions at each node [1] which includes the node itself, and [2] one which doesn't include the node. If it doesn't include the node, it will have to include all child nodes since all edges need to be covered. If it includes this node, it may include some subset of child nodes. Either way, the solution at each node is the complete solution for that subtree.

    ReplyDelete