Optimal Vertex Cover for a Tree (Linear-Time-Algorithm)

A vertex cover of an undirected graph G is a set of vertices such that each edge in G is adjacent to at least on vertex from the vertex cover.


An optimal vertex cover of a graph G is a minimum-size vertex cover of G.


The problem of finding an optimal vertex cover of a given graph is called the vertex-cover problem. This problem is a NP-Hard problem, meaning there is no polynomial-time algorithm that has been found to solve the problem. For some instances of the problem it is impossible to find an algorithm that finds a correct answer quickly enough before we turn old and die :) or before the universe runs out of fuel and disappears.


However, any instance of this problem for which the graph G is a tree is easily solvable in linear-polynomial time, meaning we can find a solution very quickly. Finding an optimal vertex cover for a tree can be solved in linear-time. Today I am going to provide an example of an algorithm that solves this problem in linear-time.


I am going to provide the actual code in C++, but before that let's quickly go over the algorithm and explain why it works as I say it does.


I am going to start by introducing a definition and a theorem.
First, a matching M for a graph G is a set of edges such that no vertex in G is adjacent to more than one edge in M. Each vertex in G is adjacent to either one edge in M or zero edges in M. Meaning each vertex in the matching M is matched to only one vertex in M.


A maximal matching M for a graph G is a matching in G such that every edge that is not in M is adjacent to at least one edge that is in M.


Then I present a theorem that says: The size of a maximal matching of a every graph G is a lower bound on the size of the optimal vertex cover of G. Meaning, an optimal vertex cover of a given graph can never have a size smaller than the graph's maximal matching size. The proof for this theorem is pretty evident so I am not going to prove it.


I found out, as so many others have done before me, that the size of a maximal matching in a tree is equals to the size of the optimal vertex cover in a tree.


My algorithm does the following:
Starting from any arbitrary node in a given tree T, and making this node the root of the tree for all purposes, do a full walk of the tree. Every time you return from a child node, check if the child node and the parent of the node have been matched. If none of them have been matched then go ahead and match them and add the edge between them to the matching, and add the parent node to the vertex cover. When the full walk returns to the root, we have constructed a vertex cover with size equal to a maximal matching of the tree. We constructed a maximal matching by adding each on of the edges that we added when we matched a child node and its parent.


See that each edge of the tree that was not added to the matching is necessarily adjacent to an edge in the matching (because if it wasn't then we would have added the edge to the matching and one of its adjacent nodes to the vertex cover, the highest hierarchy node of the two).


Since the algorithm returns a vertex cover with size equals to a maximal matching of the tree, then we can go ahead and accept this vertex cover as optimal, since no vertex cover can be smaller than that.


All right, here the code:



#include <vector>
using namespace std;


void dfsTree(vector<vector<int>> & G, 
vector<bool> & visited, 
vector<bool> & matched, 
vector<int> & minCover,
int current)
{
visited[current] = true;


for(int i = 0; i < G[current].size(); i++)
{
int childNode = G[current][i];
if( !visited[childNode] )
{
dfsTree(G, visited, matched, minCover, childNode);


if(!matched[childNode] && !matched[current])
{
//add edge to matching by adding 
                                //both of its adjacent vertices
matched[current] = true;
matched[childNode] = true;


//push father node into vertex cover
minCover.push_back(current);
}
}
}
}


vector<int> GetTreeMinVertexCover (vector<vector<int>> & G)
{
vector<bool> visited(G.size(), false);
vector<bool> matched(G.size(), false);
vector<int> minCover;


int start = 0; // any arbitrary node... really
dfsTree(G, visited, matched, minCover, start);


return minCover;
}

-------------------------------


So yeah all you have to do is provide GetTreeMinVertexCover with a tree in the form of an adjacency list and done.


So I prepared a couple of runs with different cases:



vector<int> commaSeparatedStringToIntVector(string str)
{
vector<int> vec;


while(str.length() > 0)
{
int pos = str.find(",");
if (pos!=string::npos)
{
string strNum = str.substr(0, pos);
vec.push_back(atoi(strNum.c_str()));
str = str.substr(pos+1);
}
else
{
vec.push_back(atoi(str.c_str()));
break;
}
}


return vec;
}


void Run1()
{
vector<string> adj;
adj.push_back("1");
adj.push_back("0,2");
adj.push_back("1,3");
adj.push_back("2,4");
adj.push_back("3,5");
adj.push_back("4");
vector<vector<int>> tree;

for(int i = 0; i < adj.size(); i++)
{
tree.push_back( commaSeparatedStringToIntVector(adj[i]) );
}

vector<int> minCover = GetTreeMinVertexCover(tree);
printf("minCoverSize = %d\n", minCover.size());
for(int i = 0; i < minCover.size(); i++)
{
printf("%d ", minCover[i]);
}
printf("\n-----------------\n");
}


void Run2()
{
vector<string> adj;
adj.push_back("1,2");//0
adj.push_back("0,3,4,5");//1
adj.push_back("0,6,7");//2
adj.push_back("1");//3
adj.push_back("1,8,9");//4
adj.push_back("1");//5
adj.push_back("2,10");//6
adj.push_back("2");//7
adj.push_back("4");//8
adj.push_back("4,11");//9
adj.push_back("6");//10
adj.push_back("9");//11
vector<vector<int>> tree;

for(int i = 0; i < adj.size(); i++)
{
tree.push_back( commaSeparatedStringToIntVector(adj[i]) );
}

vector<int> minCover = GetTreeMinVertexCover(tree);
printf("minCoverSize = %d\n", minCover.size());
for(int i = 0; i < minCover.size(); i++)
{
printf("%d ", minCover[i]);
}
printf("\n-----------------\n");
}


int main ()
{
Run1();
Run2();
}

---------------------


I added a little function that parses a comma-separated list of integers into a vector of integers to help myself out creating those vector of vector of integers.


The output this gives looks like this:

I guess you can use this code any time. If you find any bugs crawling around blame it on me and only on me of course :) , but I doubt this simple piece of code could have any serious mistakes, but it is certainly vulnerable to my human errors.


QED?

Fundamental Geometry Theorems and Proofs: Episode I.8

Today I am gonna go over another geometry theorem very closely related to the one solved in the last post, and I am going to prove it as well.


Here it is:
Let M be a point inside a circle C. The point M has a distance of a from the center of the circle C.
Let R be the radius of the circle. Then R > a.
Let any cord |AB| in the circle pass through M.
Prove that |MA|*|MB| = R^2 - a^2

--------------------------------------------
I now provide a proof using the Law of Cosines.


Let point O be the center of circle C.
Let angle OMA = θ

Then:


R^2 = a^2 + (|MA|^2) - 2a cos(θ)


R^2 = a^2 + (|MB|^2) - 2a cos(180 - θ)


------------------------
same as:

R^2 = a^2 + (|MA|^2) - 2a cos(θ)

R^2 = a^2 + (|MB|^2) + 2a cos(θ)

------------------------

then

R^2 - a^2 = (|MA|^2) - 2a cos(θ) = (|MB|^2) + 2a cos(θ)

hence:

(|MA| - |MB|)*(|MA| + |MB|) = 2a cos(θ)*(|MA| + |MB|)

simplifying some terms we get:

(|MA| - |MB|) = 2a cos(θ)

and then

|MA| = |MB| + 2a cos(θ)

multiply both sides by |MA| and:

|MA|^2 = |MA|*|MB| + 2a |MA| cos(θ)

So:

|MA|*|MB| = |MA|^2 - 2a |MA| cos(θ)

therefore:

|MA|*|MB| = R^2 - a^2

QED time!!!

Fundamental Geometry Theorems and Proofs: Episode I.7

Today I prove a simple euclidean geometry theorem.

Let point M be a point outside a circle C that has radius R. Let a be the distance between the point M and the center of the circle C.

Prove that for any line that passes through the point M, and that cuts the circle C in two points A and B, it happens that |MA|*|MB| has a constant value of (a^2 - R^2) for any A,B.

Where |MA| is the distance from M to A and

           |MB| is the distance from M to B.

Proof:

Let T be a point in the border of the circle C such that it is also in one of the two possible tangent lines to circle C that pass through point M. Then the line |MT| is perpendicular to the radius of the circle passing through point T, 

and hence we have |MT|^2 + R^2 = a^2 as shown below thanks to Pythagoras.

Then we can derive that a^2 - R^2 = |MT|^2 from that.

Now all we have to do is prove that |MT|^2 = |MA|*|MB| and we'd be done.

Let's do just that. Take now only into consideration the circle C, the line |MT|, and the line through M,A, and B.

Look now at triangles MAT and  MTB see that they are similar triangles.  

Angles    MTA = MBT because they are both angles with vertex in the border of the circle C and they are both opposed to the same arc.

Angle MTA is a common angle for both triangles MAT and  MTB.

Hence we have that  ( |MA| / |MT| ) = ( |MT| / |MB| ) which is the same as
|MT|^2 = |MA|*|MB|.



QED.