Vertex cover problem

In the mathematical discipline of graph theory, a vertex cover (sometimes node 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.

Formally, a vertex cover ${\displaystyle V'}$ of an undirected graph ${\displaystyle G=(V,E)}$ is a subset of ${\displaystyle V}$ such that ${\displaystyle uv\in E\Rightarrow u\in V'\lor v\in V'}$, that is to say it is a set of vertices ${\displaystyle V'}$ where every edge has at least one endpoint in the vertex cover ${\displaystyle V'}$. Such a set is said to cover the edges of ${\displaystyle G}$. The following figure shows two examples of vertex covers, with some vertex cover ${\displaystyle V'}$ marked in red.

...
Wikipedia