Vertex Cover Problem

Introduction

In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem that has an approximation algorithm.

Definition

Formally, a vertex cover V’ of an undirected graph G = (V,E) is a subset of V such that uv ∈ E ⇒ u ∈ V’ ∨ v ∈ V’, that is to say it is a set of vertices V’ where every edge has at least one endpoint in the vertex cover V’. Such a set is said to cover the edges of G.

The lower figure shows two examples of vertex covers, with some vertex cover V’ marked in red.

A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number τ is the size of a minimum vertex cover, i.e. τ =|V’|.

The lower figure shows examples of minimum vertex covers in the previous graphs.

Algorithm

There are several algorithms for determining a vertex cover. Here’s a psuedocode description of an algorithm that gives an approximate vertex cover using ideas from matching and greedy algorithms. Because the vertex cover problem is NP-complete finding an exact answer is very difficult and time consuming. Many times, approximation algorithms are useful.

Pseudocode

def greedy(E,V)

C = { }

while E not empty:

select any edge with endpoints (u,v) from E

add (u,v) to C

remove all edges incident to u or v from E

return C

Example

Kőnig’s Theorem

In the mathematical area of graph theory, Kőnig’s theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

Applications

Some problems that use ideas of vertex cover have additional and/or modified constraints compared to vertex cover. For example “The Traveling Salesman Problem” is a problem that uses a fairly straight-forward vertex cover approach.