The Dual Problem of Minimum Vertex Cover

Suppose neighborhood surveillance is required for a network that consists of streets meeting at junctions. We’d like to install the smallest number of cameras at the junctions so that all the streets can be surveilled. Such a neighborhood can be modeled as a graph by considering the junctions as vertices and the streets as edges.

The problem then is to find the smallest set of vertices (junctions) that provide a cover to all edges (streets), and this problem is known as the minimum vertex cover problem.

Vertex cover

A vertex cover of a graph $G$ is a set of its vertices such that every edge of $G$ is incident with at least one vertex in that set. A vertex in the vertex cover is said to cover all the edges incident on it. The following illustration shows three different vertex covers for the same graph.

For each of the three examples, notice how every edge is covered by some vertex in the vertex cover.

By definition, the entire vertex set of a graph is clearly also a vertex cover. We are typically interested in a vertex cover with the smallest size—a minimum vertex cover. A minimum vertex cover of the graph shown above has size three.