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 ...