Vertex

In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
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.
Vertex cover problems have been generalized to hypergraphs, see Vertex cover in hypergraphs.

View More On Wikipedia.org