The Vertex Cover Problem

Description

A vertex cover of a graph $G$ is a set $C$ of vertices such that every edge of $G$ has at least one endpoint in $C$. The vertex cover problem is to find a minimum-size vertex cover in a given graph $G$.

Related Problems

Subproblem: The Vertex Cover Problem, Degrees Bounded By 3

Parameters

$n$: number of vertices

$m$: number of edges

$k$: size of vertex cover

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Brute force (backtracking search)	1940	$O({2}^k n^O({1})$)	$O(k)$	Exact	Deterministic
Sam Buss	1993	$O(kn + {2}^k k^{({2}k + {2})})$	$O(k^{2})$?	Exact	Deterministic	Time
Chen; I. Kanj; and W. Jia.	2001	$O(kn + {1.2852}^k)$	$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)	Exact	Deterministic	Time
Chandran and F. Grandoni	2004	$O(min({1.2759}^k k^{1.5}, {1.2745}^k k^{4}) + kn)$	$O(min({1.2759}^k k^{1.5}, {1.2745}^k k^{4}) + kn)$ but exponential	Exact	Deterministic	Time & Space
Chen; I. Kanj; and W. Jia.	2006	$O({1.2738}^k+ kn)$	$O(poly(n))$	Exact	Deterministic	Time & Space
J. Chen; L. Liu; and W. Jia.	2000	$O(k*{1.2192}^k)$	$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)	Exact	Deterministic	Time
Balasubramanian; Fellows	1996	$O(kn + ({1.324718})$^k * k^{2})	$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)	Exact	Deterministic	Time
Papadimitriou and M Yannakakis	1996	$O({3}^k n)$	$O(k)$ auxiliary?	Exact	Deterministic	Time
Niedermeier, Rossmanith	1999	$O(kn + {1.29175}^k k^{2})$.	$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)	Exact	Deterministic	Time
Downey	1998	$O(kn + {1.31951}^k k^{2})$	$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)	Exact	Deterministic	Time
Exhaustive search	1940	$O(C(n, k)$) (i.e. (n, k) binomial coefficient)	$O(k)$ auxiliary	Exact	Deterministic
Downey, Fellows	1995	$O(kn+{2}^k k^{2})$	$O(k^{2})$ auxiliary	Exact	Deterministic	Time
Papadimitriou and M Yannakakis + Buss	1996	$O({3}^k k^{2}+kn)$	$O(k^{2})$ auxiliary?	Exact	Deterministic	Time
Stege, Fellows	1999	$O(kn+max(({1.25542})$^k k^{2}, ({1.2906})^k k)	$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)	Exact	Deterministic	Time
Stege, Fellows + Interleaving method (Niedermeier, Rossmanith)	2000	$O(kn+({1.2906})$^k)	$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??)	Exact	Deterministic	Time

Time Complexity Graph