graph-vertex cover

[megan0320]

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.

[megan0320]

// A dynamic programmic based solution that returns size of the minimum vertex cover.
int vertexCover(struct node *root) 
{
    // The size of minimum vertex cover is zero if tree is empty or there is only one node i.e. root.
    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 != -1)
        return root->vc;

    // Calculate size of vertex cover when root is part of it 
    int size_root_inc = 1 + vertexCover(root->left) + vertexCover(root->right);

    // Calculate size of vertex cover when root is not part of it
    int size_root_exc = 0;
    if (root->left)
    size_root_exc += 1 + vertexCover(root->left->left) + vertexCover(root->left->right); 
    if (root->right) 
    size_root_exc += 1 + vertexCover(root->right->left) + vertexCover(root->right->right); 

    // Minimum of two values is vertex cover, store it before returning.
    root->vc = min(size_root_inc, size_root_exc); 

    // returning minimum of the two.
    return root->vc; 
}