In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. 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. Its decision version, the vertex cover problem, was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in computational complexity theory. Furthermore, the vertex cover problem is fixed-parameter tractable and a central problem in parameterized complexity theory.
The minimum vertex cover problem can be formulated as a half-integral linear program whose dual linear program is the maximum matching problem.
| Covering-packing dualities | |
| Covering problems | Packing problems |
|---|---|
| Minimum set cover | Maximum set packing |
| Minimum vertex cover | Maximum matching |
| Minimum edge cover | Maximum independent set |
Read more about Vertex Cover: Definition, Computational Problem, Vertex Cover in Hypergraphs
Famous quotes containing the word cover:
“There is nothing more poetic and terrible than the skyscrapers’ battle with the heavens that cover them. Snow, rain, and mist highlight, drench, or conceal the vast towers, but those towers, hostile to mystery and blind to any sort of play, shear off the rain’s tresses and shine their three thousand swords through the soft swan of the fog.”
—Federico García Lorca (1898–1936)