# Vertex cover
A **vertex cover** of an undirected graph G = (V, E) is a subset of the vertices that contains at least one endpoint of every edge[1](https://link.springer.com/article/10.1007/s00224-012-9393-4). The decision problem Vertex Cover takes a graph G and an integer k and asks whether G has a vertex cover of size at most k[1](https://link.springer.com/article/10.1007/s00224-012-9393-4). The problem is one of the six classic NP-complete problems in the work of Garey and Johnson on intractability, and it has played an important role in the development of parameterized algorithms[1](https://link.springer.com/article/10.1007/s00224-012-9393-4). [Richard M. Karp](https://www.edgepedia.org/richard-m-karp)'s 1972 paper "Reducibility Among Combinatorial Problems", published in the proceedings of a symposium at the IBM Thomas J. Watson Research Center (pages 85–103, Plenum Press), is the classical reference for its [NP-completeness](https://www.edgepedia.org/np-completeness)[2](https://researchr.org/publication/Karp72/bibtex).
| Key fact | Detail |
|---|---|
| Definition | A subset of vertices containing at least one endpoint of every edge; the decision version asks for a cover of size at most k[1](https://link.springer.com/article/10.1007/s00224-012-9393-4) |
| Complexity | NP-complete; among the six classic NP-complete problems of Garey and Johnson[1](https://link.springer.com/article/10.1007/s00224-012-9393-4) |
| Bipartite case | Solvable in polynomial time: by Kőnig's theorem, the size of a maximum matching equals the size of a minimum vertex cover[3](https://arxiv.org/abs/2004.08636) |
| Approximation | The greedy algorithm always finds a cover within a factor of two of the optimum[4](https://tanktechnology.github.io/CLRS-Lean/CLRSLean/FourthEdition/Chapter_35/Section_35_1_The_Vertex_Cover_Problem/) |
| FPT exponents cited | O*(1.129175k) by Niedermeier et al.[5](https://link.springer.com/article/10.1186/s13673-020-00226-w); a 2024 algorithm reaches O*(1.2575k) with a simpler design[6](https://drops.dagstuhl.de/storage/00lipics/lipics-vol289-stacs2024/LIPIcs.STACS.2024.40/LIPIcs.STACS.2024.40.pdf) |
| Hardness of approximation | On degree-d graphs, Unique Games-hard within 2 − (2+o_d(1)) · loglog d / log d[7](https://toc.cs.uchicago.edu/articles/v007a003/) |
| Applications | Bioinformatics[1](https://link.springer.com/article/10.1007/s00224-012-9393-4); wireless sensor network tasks such as link-failure monitoring, facility location, clustering, and data aggregation[8](https://arxiv.org/abs/1402.2140) |
## Computational status
Computing a minimum vertex cover is NP-hard, so no polynomial-time algorithm is expected to solve the problem exactly on general graphs unless P = NP[4](https://tanktechnology.github.io/CLRS-Lean/CLRSLean/FourthEdition/Chapter_35/Section_35_1_The_Vertex_Cover_Problem/). Because the problem has a simple structure, it has served as an ideal testbed for new techniques in parameterized complexity[1](https://link.springer.com/article/10.1007/s00224-012-9393-4). A parameterized problem is fixed-parameter tractable (FPT) if an instance (x, k) can be decided in time f(k)·|x|c for some computable function f and constant c[1](https://link.springer.com/article/10.1007/s00224-012-9393-4), and Vertex Cover parameterized by the solution size k is the canonical example of an FPT problem.
## Exact and parameterized algorithms
**Branching.** The simplest parameterized algorithm is a recursive bounded search tree: pick a vertex v and branch on either including v in the cover or discarding v and including all of its neighbors, giving O*(2n) time in the naive form[9](https://www.sciencedirect.com/science/article/am/pii/S030439751500852X). Decades of refinement have produced much better exponents. A survey of parameterized algorithms credits Niedermeier and coauthors with an O*(1.129175k)-time FPT algorithm for Vertex Cover[5](https://link.springer.com/article/10.1186/s13673-020-00226-w). A 2024 STACS paper presents a relatively simple algorithm with runtime O*(1.2575k), whose key idea is a potential function that simultaneously tracks k and the optimal value λ of the vertex cover LP relaxation[6](https://drops.dagstuhl.de/storage/00lipics/lipics-vol289-stacs2024/LIPIcs.STACS.2024.40/LIPIcs.STACS.2024.40.pdf). A spectrum of tractability exists for FPT problems under the Exponential-Time Hypothesis (assumption that no algorithm avoids exponential search time), from slightly sub-exponential 2O(√k)·nO(1) time for Planar Vertex Cover through single-exponential 2O(k)·nO(1) time for Vertex Cover itself[10](https://www.mdpi.com/1999-4893/13/6/146).
**Practice.** Branch-and-reduce algorithms, which combine many branching and reduction rules, hold the best theoretical time bounds for problems including Independent Set (equivalently, Vertex Cover). A 2016 case study implemented such an algorithm for Vertex Cover and compared it with a commercial integer programming solver (CPLEX 12.6) and the branch-and-bound maximum-clique solver MCS run on complement graphs; the results showed that branch-and-reduce algorithms are practical and competitive on several kinds of instances[9](https://www.sciencedirect.com/science/article/am/pii/S030439751500852X). The winning solver of the PACE 2019 Challenge, Vertex Cover Track, used a portfolio of aggressive kernelization, local search, branch-and-reduce, and a state-of-the-art branch-and-bound solver, and several of its techniques came from the literature on the complementary maximum independent set and maximum clique problems[11](https://epubs.siam.org/doi/10.1137/1.9781611976229.1).
## Approximation
The greedy APPROX-VERTEX-COVER algorithm always finds a cover within a factor of two of the optimum, even though computing a minimum vertex cover is NP-hard[4](https://tanktechnology.github.io/CLRS-Lean/CLRSLean/FourthEdition/Chapter_35/Section_35_1_The_Vertex_Cover_Problem/). This guarantee is essentially matched from below on bounded-degree graphs: Per Austrin, Subhash Khot, and Muli Safra proved that on degree-d graphs, Vertex Cover is Unique Games-hard to approximate within a factor 2 − (2+o_d(1)) · loglog d / log d, which matches the algorithmic result of Halperin (SICOMP 2002) up to the o_d(1) term[7](https://toc.cs.uchicago.edu/articles/v007a003/).
Variants carry their own approximation landscape. For Minimum Sum Vertex Cover, a variant that is NP-hard in its own right, the best-known polynomial-time approximation factor is 16/9, due to Bansal, Batra, Farhadi, and Tetali (SODA 2021)[12](https://arxiv.org/abs/2401.05085).
## Kernelization
**Kernelization** is a preprocessing technique of parameterized algorithms: a set of reduction rules applied in polynomial time that shrinks an instance while preserving the answer, and it can also produce reduced instances with special properties that help FPT algorithms[5](https://link.springer.com/article/10.1186/s13673-020-00226-w). A fundamental result in fixed-parameter tractability is that a problem parameterized by k is FPT if and only if it admits a kernelization algorithm for the same parameter[10](https://www.mdpi.com/1999-4893/13/6/146).
Crown decomposition, proposed early in the history of parameterized computation, has been applied successfully in the kernelization of Vertex Cover and later of many other problems[5](https://link.springer.com/article/10.1186/s13673-020-00226-w). A crown in a graph G = (V, E) is a triple (I, H, R) of disjoint sets with V = I ∪ H ∪ R, where I is a nonempty independent set and H is the neighbor set of I[5](https://link.springer.com/article/10.1186/s13673-020-00226-w).
A survey by Michael R. Fellows, Lars Jaffke, Aliz Izabella Király, Frances A. Rosamond, and Mathias Weller discusses the **Barrier Degree** of Vertex Cover kernelization: reduction rules exist that kernelize vertices of small degree, including results that reduce graphs almost to minimum degree five, and the survey asks what minimum vertex-degree barrier exists for polynomial-time kernelization. Assuming the Exponential-Time Hypothesis, such a minimum degree barrier exists[13](https://arxiv.org/abs/1811.09429). The same survey reports the first experimental results of an AI-guided branching algorithm for Vertex Cover whose logic appears amenable to finding reduction rules for small-degree vertices[13](https://arxiv.org/abs/1811.09429).
Kernel size also depends on the parameter chosen. Under the refined parameterization by the feedback vertex set number fvs(G), the size of a smallest vertex set whose deletion turns G into a forest, the unweighted Vertex Cover problem admits a polynomial kernel, while the weighted variant with non-negative integral vertex weights has only a conditional superpolynomial lower bound on kernel size[1](https://link.springer.com/article/10.1007/s00224-012-9393-4). Kernelization results extend beyond the problem itself: many problems, such as q-Coloring, Odd Cycle Transversal, and Chordal Deletion, admit polynomial kernels when parameterized by the size of a given vertex cover of the input[14](https://www.sciencedirect.com/science/article/pii/S0022000013001682).
## Vertex cover as a graph parameter
Beyond being a problem, the vertex cover number serves as a structural parameter for other graph problems, since it handles graphs that are hard when parameterized by tree-width. Its drawback is that bounding it severely restricts admissible graph classes. Robert Ganian of Vienna University of Technology introduced the generalization **twin-cover**, which imposes a lesser restriction on graph structure and attains low values even on dense graphs; a wide range of difficult problems admit FPT algorithms when parameterized by twin-cover, and MS1 model checking can be done in elementary FPT time under this parameter[15](https://dmtcs.episciences.org/en/articles/2136).
## The bipartite case
[Kőnig's theorem](https://www.edgepedia.org/konigs-theorem-graph-theory) states that in bipartite graphs, the size of a maximum matching equals the size of a minimum vertex cover[3](https://arxiv.org/abs/2004.08636). This equality makes the minimum vertex cover problem efficiently solvable on bipartite graphs: one finds a maximum matching and constructs a minimum cover from it[3](https://arxiv.org/abs/2004.08636). The theorem is a celebrated result of early combinatorics, and algorithms for the maximum flow problem can be used to solve the bipartite matching problem that underlies it[3](https://arxiv.org/abs/2004.08636).
## Variants and applications
The problem has many constrained and generalized forms. Connected Vertex Cover is FPT when parameterized by the solution size but is unlikely to have a polynomial-sized kernel under complexity-theoretic assumptions; α-approximate (lossy) kernels exist for every α > 1[16](https://arxiv.org/abs/1711.07872). The 3-path vertex cover problem, which asks for vertices hitting all paths of three vertices, has a parameterized algorithm running in O*(1.713k) time[17](https://arxiv.org/abs/1809.02636).
Applications reach into several domains. Vertex Cover has a documented role in bioinformatics[1](https://link.springer.com/article/10.1007/s00224-012-9393-4), and vertex covering supports wireless sensor network tasks including monitoring link failures, facility location, clustering, and data aggregation[8](https://arxiv.org/abs/1402.2140).
## References
1. [Vertex Cover Kernelization Revisited, Theory of Computing Systems (Springer)](https://link.springer.com/article/10.1007/s00224-012-9393-4)
2. [Reducibility Among Combinatorial Problems, Richard M. Karp (1972), researchr bibliography](https://researchr.org/publication/Karp72/bibtex)
3. [Mapping Matchings to Minimum Vertex Covers: Kőnig's Theorem Revisited, arXiv](https://arxiv.org/abs/2004.08636)
4. [The Vertex-Cover Problem, CLRS-Lean, Section 35.1](https://tanktechnology.github.io/CLRS-Lean/CLRSLean/FourthEdition/Chapter_35/Section_35_1_The_Vertex_Cover_Problem/)
5. [Parameterized algorithms of fundamental NP-hard problems: a survey, Human-centric Computing and Information Sciences (Springer)](https://link.springer.com/article/10.1186/s13673-020-00226-w)
6. [A Faster Algorithm for Vertex Cover Parameterized by Solution Size, STACS 2024 (LIPIcs vol. 289)](https://drops.dagstuhl.de/storage/00lipics/lipics-vol289-stacs2024/LIPIcs.STACS.2024.40/LIPIcs.STACS.2024.40.pdf)
7. [Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs, Theory of Computing, Volume 7 (2011), Article 3](https://toc.cs.uchicago.edu/articles/v007a003/)
8. [Distributed Vertex Cover Algorithms For Wireless Sensor Networks, arXiv](https://arxiv.org/abs/1402.2140)
9. [Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover, Theoretical Computer Science](https://www.sciencedirect.com/science/article/am/pii/S030439751500852X)
10. [A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms, Algorithms (MDPI)](https://www.mdpi.com/1999-4893/13/6/146)
11. [WeGotYouCovered: The Winning Solver from the PACE 2019 Challenge, Vertex Cover Track, SIAM CSC 2020 Proceedings](https://epubs.siam.org/doi/10.1137/1.9781611976229.1)
12. [Parameterized Algorithms for Minimum Sum Vertex Cover, arXiv](https://arxiv.org/abs/2401.05085)
13. [What is known about Vertex Cover Kernelization? Fellows, Jaffke, Király, Rosamond, Weller, arXiv](https://arxiv.org/abs/1811.09429)
14. [Preprocessing subgraph and minor problems: When does a small vertex cover help?, Journal of Computer and System Sciences (ScienceDirect)](https://www.sciencedirect.com/science/article/pii/S0022000013001682)
15. [Improving Vertex Cover as a Graph Parameter, Robert Ganian, Discrete Mathematics & Theoretical Computer Science, vol. 17:2](https://dmtcs.episciences.org/en/articles/2136)
16. [Revisiting Connected Vertex Cover: FPT Algorithms and Lossy Kernels, arXiv](https://arxiv.org/abs/1711.07872)
17. [Parameterized algorithm for 3-path vertex cover, arXiv](https://arxiv.org/abs/1809.02636)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Computational graph problems and algorithms › NP-hard graph problems and their algorithms*
*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Oct 15, 2026; Oct 25, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license