Vertex Cover

Input

Graph $G = (V, E)$, positive integer $K \leq |V|$.

Question

Is there a vertex cover of size $K$ or less for $G$, i.e. a subset $V' \subseteq V$ with $|V'| \leq K$ such that for each edge $\{u,v\} \in E$ at least one of $u$ and $v$ belongs to $V'$?

Classes

• NP-complete

Comments

Equivalent complexity to Independent Set with respect to restrictions on $G$. Variation in which the subgraph induced by $V'$ is required to be connected is also NP-complete, even for planar graphs with no vertex degree exceeding 4 (Garey & Johnson, 1977). Easily solved in polynomial time if $V'$ is required to be both a vertex cover and an independent set for $G$. The related [problem:edge-cover] problem, in which one wants the smallest set $E' \subseteq E$ such that every $v \in V$ belons to at least on $e \in E'$, can be solved in polynomial time by graph matching (e.g. see (Lawler, 1976))

Proofs

NP-complete

Transformation from 3-Satisfiability (Karp, 1972).

Reducible from

• 3-Satisfiability

Reducible to

• Clique
• Directed Hamiltonian Circuit
• Dominating Set
• Feedback Arc Set
• Feedback Vertex Set
• Hamiltonian Circuit
• Hamiltonian Path
• Hitting Set
• Independent Set
• Minimum Maximal Matching
• Partial Feedback Edge Set
• Uniconnected subgraph

References

• Garey, M. R., & Johnson, D. S. (1977). The Rectilinear Steiner Tree Problem is $NP$-Complete. SIAM Journal on Applied Mathematics, 32(4), 826–834. https://doi.org/10.1137/0132071
• Lawler, E. L. (1976). Combinatorial optimization: networks and matroids. Holt, Rinehart.
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9