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:
“Now folks, I hereby declare the first church of Tombstone, which ain’t got no name yet or no preacher either, officially dedicated. Now I don’t pretend to be no preacher, but I’ve read the Good Book from cover to cover and back again, and I nary found one word agin dancin’. So we’ll commence by havin’ a dad blasted good dance.”
—Samuel G. Engel (1904–1984)