Tree Vertex Cover Problem

Weighted Tree Vertex Cover Problem

Vertex cover of graph  G=(V,E) is defined as V'\subseteq V s.t.  \forall (u,v) \in E u \in V' \vee v \in V'. In other word a subset of the vertices such that all vertices are incident to a vertex in the vertex cover.
We will derive an algorithm for finding the weight of a minimal (yes is not unique) vertex cover for a subclass of graphs i.e. tree (which are acyclic graphs with the property that only one path between each vertex exists).

Remember that vertex cover for graphs is an NP-Complete (NP-hard and NP, hard at least as all NP problems and it is an NP problem itself) problem i.e. no deterministic polynomial tyme algorithm was discovered (if you discover one, contact me, we will be millionaire).

Tree Vertex Cover - Problem Definition

Given a weighted tree T = (V,E,f) with f : \mathcal{N^+} \rightarrow \mathcal{N^+} write an algorithm for computing a vertex cover with minimum weight i.e. V' is a vertex cover and the sum of the weight of its element is minimal.

The following is the tree structure that we will use throughout the article.

template<typename T,int DEGREE>
struct node{
       array<node*,DEGREE> children;

       T data;
       int weight;

        node(const T& v , int _weight) : weight(_weight){
               data=v;
               mincover=0;
       }
};

What if the weight is equal to the degree of the node?

The first observation we can make is that the root node can weather be or not be in the vertex cover. If we include it in the solution then we are sure that all the edges from it to its children have been covered and to solve the problem we need only to compute the cover of its children (which is a simpler problem). If not, we have to include in the cover all its children (otherwise who is gonna cover all outgoing edges from the root to the children?) plus the cover of all its grandchildren. Base cases are: 1) the empty tree (which has a cover of size zero) and 2) leaf (which has empty cover as well).

In order to make it easier to follows the following is an implementation of the tree cover on binary tree

Tree Vertex Cover for binary tree and uniform weight

int cover(node<T,2>* root){

//it is the null tree or a leaf?
if(!root || ( ( !root->children[0]) && ( root->children[1] ) ) )
return 0;

//compute the size of the cover when root is included in the cover
int sizein = 1 + cover(root->children[0]) + cover(root->children[1]);

//compute the size of the cover when root is NOT included in the cover
int sizeex =
( (root->children[0]) ? ( 1 + cover(root->children[0]->children[0]) + cover(root->children[0]->children[1]) ) : 0 )
+
( (root->children[1])? ( 1 + cover(root->children[1]->children[0]) + cover(root->children[1]->children[1]) ) : 0 );

return min(sizein,sizeex);
}

This logic can be easily applied to n-ary tree.


bool isLeaf(node<T,DEGREE>* root){
for(int i=0 ; i<DEGREE;i++) if(root->children[i])
    return false;
return true;
}

template<class T, int DEGREE>
int cover(node<T,DEGREE>* root){

//it is the null tree or a leaf?
if(!root || isLeaf(root) )
   return 0;

//compute the size of the cover when root is included in the cover
int sizein = 1 ;
for(int i=0 ; i<DEGREE;i++) sizein += cover(root->children[i]);


//compute the size of the cover when root is NOT included in the cover
int sizeex = 0;
for(int i=0 ; i<DEGREE;i++){ if(root->children[i]){
      sizeex+=1;
   for(int j=0 ; j<DEGREE;j++) sizeex += cover(root->children[i]->children[j]);
  }
}

return min(sizein,sizeex);
}

As the last step, let's weights come into play. What if we want to find the cover with minimal weight? Well, the problem of finding the cover with the smallest number of elements is in fact, an instance of the weighted cover problem where all the weight are the same across all the nodes in the tree (we add on whenever we choose a node to be inserted in the cover).
The trick is to use the node weight during the evaluation phase of the weight of the cover. Here's the code which takes into consideration the weights and finds the cover with minimal weight (which can be a different respect to the one with minimal number of elements)

template<class T, int DEGREE>
int cover(node<T,DEGREE>* root){

//it is the null tree or a leaf?
if(!root || isLeaf(root) )
   return 0;

//compute the size of the cover when root is included in the cover
int sizein = root->weight ;
for(int i=0 ; i<DEGREE;i++) sizein += cover(root->children[i]);


//compute the size of the cover when root is NOT included in the cover
int sizeex = 0;
for(int i=0 ; i<DEGREE;i++){ if(root->children[i]){
      sizeex+=root->children[i]->weight;
   for(int j=0 ; j<DEGREE;j++) sizeex += cover(root->children[i]->children[j]);
  }
}
return min(sizein,sizeex);
}

Note that the solution proposed is not efficient. It has in fact, exponential complexity! Luckily there is a way using Dynamic Programming for lowering the complexity to polynomial.
Note that a lot of subproblems are recomputed over and over using this approach. Memoization will do the job.

To conclude the following is a test main() for the functions above.


int main(){
  struct node<int,2>* root = new node<int,2>(1,2);
  root->children[0] =  new node<int,2>(2,3);
  root->children[0]->children[0] =  new node<int,2>(4,1);
  root->children[0]->children[1] =  new node<int,2>(5,3);
  root->children[0]->children[1]->children[0] =  new node<int,2>(6,1);
  root->children[0]->children[1]->children[1] =  new node<int,2>(7,1);

  root->children[1] =  new node<int,2>(3,2);
  root->children[1]->children[1] = new node<int,2>(8,1);
cout<<cover(root)<<endl;
  return 0;
}


Be the first to leave a comment. Don’t be shy.

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>