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:
“I wouldn’t pray just for a old man that’s dead because he’s all right. If I was to pray, I’d pray for the folks that’s alive and don’t know which way to turn. Grampa here, he ain’t got no more trouble like that. He’s got his job all cut out for him. So cover him up and let him get to it.”
—Nunnally Johnson (1897–1977)