Vertex Cover Problem | Set 2 (Dynamic Programming Solution for Tree) - GeeksforGeeks
A vertex cover of an undirected graph is a subset of its vertices such that for every edge (u, v) of the graph, either 'u' or 'v' is in vertex cover. Although the name is Vertex Cover, the set covers all edges of the given graph.
The problem to find minimum size vertex cover of a graph is NP complete. But it can be solved in polynomial time for trees. In this post a solution for Binary Tree is discussed. The same solution can be extended for n-ary trees.
http://isharemylearning.blogspot.com/2012/07/minimum-vertex-cover-of-tree.html
Tree is a special type of graph which has no cycles and so it's possible to find out the minimum vertex cover by using Dynamic Programming.
Basic idea is if any vertex is included in the set, we are free to choose or not choose it's children but if any vertex isn't included in set then we have to choose all the children of it.
Recursive Solution:
http://algorithmsonlineresources.blogspot.com/2013/03/minimum-vertex-cover-problem.html
private static void calcVertexCover(int index) {
if (index == (-1)) {
checkVertexCover();
} else {
arr[index] = false;
calcVertexCover(index - 1);
arr[index] = true;
calcVertexCover(index - 1);
}
}
http://www.cs.mun.ca/~harold/Courses/Old/CS3719.W08/Diary/VCST.java
DFS+Greedy
Proof: http://cs.stackexchange.com/questions/12177/correctness-proof-of-a-greedy-algorithm-for-minimum-vertex-cover-of-a-tree
http://tristan-interview.blogspot.com/2012/03/find-minimun-vertex-cover-for-tree.html
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:
http://xiadejun.blogspot.com/2012/12/minimum-vertex-covermaximum-independent.html
由树叶往树根方向开始选出Vertex Cover 的点，如果一个节点与其父节点都没有选中，也就表示他们之间的边没有被覆盖到，也就表示必须要从两点中选出一点作为Vertex Cover 的点，而选择父节点一定是比较好的。时间复杂度等同于一次Graph Traversal 的时间。
一、利用DFS找出preorder，并且建立DFS tree。
二、以preorder的逆序开始选出Vertex Cover的点。
Approximation Solutin:
http://massivealgorithms.blogspot.com/2015/05/vertex-cover-problem-set-1-introduction.html
Todo:
http://www.csie.ntnu.edu.tw/~u91029/Domination.html
Video:https://class.coursera.org/algo2-003/lecture/171
http://courses.csail.mit.edu/6.006/spring11/lectures/lec21.pdf
Read full article from Vertex Cover Problem | Set 2 (Dynamic Programming Solution for Tree) - GeeksforGeeks
A vertex cover of an undirected graph is a subset of its vertices such that for every edge (u, v) of the graph, either 'u' or 'v' is in vertex cover. Although the name is Vertex Cover, the set covers all edges of the given graph.
The problem to find minimum size vertex cover of a graph is NP complete. But it can be solved in polynomial time for trees. In this post a solution for Binary Tree is discussed. The same solution can be extended for n-ary trees.
http://isharemylearning.blogspot.com/2012/07/minimum-vertex-cover-of-tree.html
Tree is a special type of graph which has no cycles and so it's possible to find out the minimum vertex cover by using Dynamic Programming.
Basic idea is if any vertex is included in the set, we are free to choose or not choose it's children but if any vertex isn't included in set then we have to choose all the children of it.
The idea is to consider following two possibilities for root and recursively for all nodes down the root.
1) Root is part of vertex cover: In this case root covers all children edges. We recursively calculate size of vertex covers for left and right subtrees and add 1 to the result (for root).
1) Root is part of vertex cover: In this case root covers all children edges. We recursively calculate size of vertex covers for left and right subtrees and add 1 to the result (for root).
2) Root is not part of vertex cover: In this case, both children of root must be included in vertex cover to cover all root to children edges. We recursively calculate size of vertex covers of all grandchildren and number of children to the result (for two children of root).
Dynamic Programming: Using Memoization.
an additional field ‘vc’ is added to tree nodes. The initial value of ‘vc’ is set as 0 for all nodes. The recursive function vCover() calculates ‘vc’ for a node only if it is not already set.
Java code(same) https://github.com/mission-peace/interview/blob/master/src/com/interview/tree/VertexCoverBinaryTreeDP.java
Java code(same) https://github.com/mission-peace/interview/blob/master/src/com/interview/tree/VertexCoverBinaryTreeDP.java
// A memoization based function that returns size of the minimum vertex cover.int vCover(struct node *root){ // The size of minimum vertex cover is zero if tree is empty or there // is only one node if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 0; // If vertex cover for this node is already evaluated, then return it // to save recomputation of same subproblem again. if (root->vc != 0) return root->vc; // Calculate size of vertex cover when root is part of it int size_incl = 1 + vCover(root->left) + vCover(root->right); // Calculate size of vertex cover when root is not part of it int size_excl = 0; if (root->left) size_excl += 1 + vCover(root->left->left) + vCover(root->left->right); if (root->right) size_excl += 1 + vCover(root->right->left) + vCover(root->right->right); // Minimum of two values is vertex cover, store it before returning root->vc = min(size_incl, size_excl); return root->vc;}struct node{ int data; int vc; struct node *left, *right;};int vCover(struct node *root){ // The size of minimum vertex cover is zero if tree is empty or there // is only one node if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 0; // Calculate size of vertex cover when root is part of it int size_incl = 1 + vCover(root->left) + vCover(root->right); // Calculate size of vertex cover when root is not part of it int size_excl = 0; if (root->left) size_excl += 1 + vCover(root->left->left) + vCover(root->left->right); if (root->right) size_excl += 1 + vCover(root->right->left) + vCover(root->right->right); // Return the minimum of two sizes return min(size_incl, size_excl);}private static void calcVertexCover(int index) {
if (index == (-1)) {
checkVertexCover();
} else {
arr[index] = false;
calcVertexCover(index - 1);
arr[index] = true;
calcVertexCover(index - 1);
}
}
http://www.cs.mun.ca/~harold/Courses/Old/CS3719.W08/Diary/VCST.java
DFS+Greedy
Proof: http://cs.stackexchange.com/questions/12177/correctness-proof-of-a-greedy-algorithm-for-minimum-vertex-cover-of-a-tree
http://tristan-interview.blogspot.com/2012/03/find-minimun-vertex-cover-for-tree.html
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).
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;
}
}
http://xiadejun.blogspot.com/2012/12/minimum-vertex-covermaximum-independent.html
由树叶往树根方向开始选出Vertex Cover 的点，如果一个节点与其父节点都没有选中，也就表示他们之间的边没有被覆盖到，也就表示必须要从两点中选出一点作为Vertex Cover 的点，而选择父节点一定是比较好的。时间复杂度等同于一次Graph Traversal 的时间。
一、利用DFS找出preorder，并且建立DFS tree。
二、以preorder的逆序开始选出Vertex Cover的点。
Approximation Solutin:
http://massivealgorithms.blogspot.com/2015/05/vertex-cover-problem-set-1-introduction.html
Todo:
http://www.csie.ntnu.edu.tw/~u91029/Domination.html
Video:https://class.coursera.org/algo2-003/lecture/171
http://courses.csail.mit.edu/6.006/spring11/lectures/lec21.pdf
Read full article from Vertex Cover Problem | Set 2 (Dynamic Programming Solution for Tree) - GeeksforGeeks
