# Vertex cover Problem

September 18, 2009 2 Comments

Here we’ll see a simple algorithm that finds a near-optimal vertex cover of a graph.

Firstly, what is a ** vertex cover**? A vertex cover is a set of vertices, call it S, such that the following condition holds: every edge of the graph has at least one end-point in S.

( i.e. we are “covering” all the edges of the graph through the vertex cover.)

Example: If vertex, x is adjacent to vertices, a, b, and c, then it “covers” edges {x,a}, {x,b} and {x,c}.

What we ideally want is a vertex cover having the minimum number of vertices, i.e. we want to “cover” all the edges of the graph using as few vertices as possible.

That would an optimal vertex cover. So, what is meant by “near-optimal”? This means that the vertex cover we find is not exactly one of the minimum possible cardinality. However, it also means that this vertex is close in size, say by a constant multiplicative factor, to the optimal one.

Why should we settle for a solution that is not as good as optimal? The reason is simple: some questions are inherently difficult to solve exactly. Also, for some problems, a near-optimal solution is good enough.

(Note that we only consider graphs that do not have any isolated vertices.)

We digress here a bit to introduce another concept.

Consider a graph, G. Pick an edge of G. Now, pick another edge of G, that is not adjacent to the edge picked earlier (i.e. the two edges do not have any common end-points). These two edges are said to be disjoint.

A ** matching **in a graph is a set of disjoint edges.

What we would like to see is how many edges we can possibly have in a matching. A ** maximum matching** is a matching having the maximum number of edges that any matching of that particular graph can possibly have. (Note that we say “a” maximum matching, instead of “the” maximum matching, since a graph can have multiple maximum matchings.)

The vertex cover algorithm is based on two simple ideas.

*Idea 1*: If we take the end-vertices of all edges forming a maximum matching of a graph, G, then this set of vertices, say S, forms a vertex cover of G.

*Idea 1*

This is simple to prove. Assume there is an edge {x,y} which is not “covered” by S, i.e. neither x nor y is in S. In that case, we can add edge {x,y} to get a new matching. This matching has a size greater than that of our maximum matching, which is not possible. Hence, all edges of G are “covered” by S.

As stated earlier, we are interested in finding a vertex cover having minimum number of vertices. How does set S fare on this account?

*Idea 2: The size of a maximum matching of G is a lower bound on the size of a vertex cover of G. *

*Idea 2: The size of a maximum matching of G is a lower bound on the size of a vertex cover of G.*

i.e. The best possible vertex cover of G (one with least possible number of vertices) will have at least ‘k’ vertices, where ‘k’ is the number of edges in a maximum matching of G. ( k = |S| / 2, in our terminology.)

This is also easily proved. Let’s call the vertex cover as T. Now, every edge of the maximum matching, call it M, must be “covered” by T. So, every edge of M must have at least one end-vertex in T. Also, there is no overlap whatsoever among the end-vertices of any two edges of M. Therefore, T must contain at least |M| vertices.

We can’t obtain a vertex cover with lesser number of vertices.

“Idea 1” showed how to obtain a vertex cover of size, |S| = 2 |M|. And “Idea 2” showed that a minimum vertex cover needs to have at least |M| vertices.

So, what we obtained through “Idea 1” is a vertex cover that is within a factor of two from the optimal. i.e. The number of vertices it contains is no more than twice the number of vertices contained in an optimal vertex cover.

Such an algorithm is known as a factor-2 approximation algorithm.

Notes:

1. There exist algorithms that can find a maximum matching in polynomial time. (In algorithmic terms, a polynomial running time is considered to be “efficient”.) On the other hand, we do not know of any such efficient algorithm for obtaining an optimal vertex cover. Hence, we use the matching problem to develop an efficient approximation algorithm.

2. Suppose a network of roads in a town is modeled as a graph, with the streets representing edges, and intersections between streets being the vertices. We are asked to place policemen at the street intersections such that all streets are monitored by at least one policeman. ( A policeman can monitor all streets that begin/end at his intersection.) We want to use as few policemen as possible. This is the same as the optimal vertex cover problem.

It’s hard to find notes on graph theory that are this easy to read. Well done 🙂

Thank you so much for your comment. Sorry for my late reply.