What is the graph vertex cover problem?

The vertex cover of a graph is a set of nodes that cover all the edges in that graph. In other terms, it consists of vertices such that for every edge, (u,v) ∈ E, either u or v or both are a part of the set.

Here are a few examples

The following illustration shows how to find the vertex cover step by step:

As we have seen, it is not difficult to find the vertex cover of a given graph. The set of all vertices is also a vertex cover. However, problems arise when we have to find the minimum vertex coverminimum number of vertices such that all edges are covered of a given graph. Such a situation can be seen in an NP-complete problem.

There are only approximate algorithms that can solve the NP-complete problem in an efficient manner, but their solutions are very close to optimal. The difference between the approximate and optimal solution can be proved. For example, an approximate algorithm for the minimum vertex cover problem is given below. This algorithm can be proven to find the solution that is not larger than double the optimal solution.

1. Result = {empty set of nodes}

2. Repeat while the set of edges of the graph is not empty:

   2.1) Pick any edge (u,v) ∈ E

   2.2) Result = Result + u + v

   2.3) Remove the edges that have u or v as an end point

For special types of graphs (including bipartite graphs and trees), this problem can be solved in polynomial time.

Bipartite graph

To understand the algorithm for finding the minimum vertex cover of a bipartite graph, you need to learn about maximal matching first

1. Find the maximal matching of the bipartite graph
2. Result = ( P1 - Z ) ∪ ( P2 ∩ Z )

where:
P1 - first partite set
P2 - second partite set
Z - set of vertices from P1 that are either:

• not a part of the maximal matching
• connected via an alternating pathpath that consists of edges that alternate between being in the maximal matching set and not being in the maximal matching set to an unmatched vertex from P1

For example:

In this example:
P1 = { 1, 2, 3, 4, 5 }
P2 = { 6, 7, 8, 9, 10 }
Z = { 2, 4, 8 }

Here, 4 is an unmatched vertex of P1. The alternate path is 4-8-2, hence, 2 and 8 are also a part of Z.

Minimum vertex cover = { 1, 3, 5 } ∪ { 8 } = { 1, 3, 5, 8 }

Tree graph

To find the minimum vertex cover of a tree:

1. Result = {}

2. Repeat until the set of edges of the graph is not empty

   2.1) l = leaf node

   2.2) p = parent of l

   2.2) Result = Result + l + p

   2.3) Remove l and p, and all of the edges associated with them from the graph