Vertex cover

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.

Definition

Formally, a vertex cover

V

′

{\displaystyle V'}

of an undirected graph

G

=

(

V

,

E

)

{\displaystyle G=(V,E)}

is a subset of

V

{\displaystyle V}

such that

(

u

v

∈

E

)

⇒

(

u

∈

V

′

∨

v

∈

V

′

)

{\displaystyle (uv\in E)\Rightarrow (u\in V'\lor v\in V')}

, that is to say it is a set of vertices

V

′

{\displaystyle V'}

where every edge has at least one endpoint in the vertex cover

V

′

{\displaystyle V'}

.