The Dual Problem of Minimum Vertex Cover

Learn how the minimum vertex cover problem is the dual of the maximum matching problem.

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.

Get hands-on with 1200+ tech skills courses.