In 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.

In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations. It 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.

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 upper figure shows two examples of vertex covers, with some vertex cover ${\displaystyle V'}$ marked in red.

A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number ${\displaystyle \tau }$ is the size of a minimum vertex cover, i.e. ${\displaystyle \tau =|V'|}$. The lower figure shows examples of minimum vertex covers in the previous graphs.

The minimum vertex cover problem is the optimization problem of finding a smallest vertex cover in a given graph.

If the problem is stated as a decision problem, it is called the vertex cover problem: