The Vertex Cover Problem

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

Parameters

$n$ : number of vertices
$m$ : number of edges
$k$ : size of vertex cover

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 14 of 14 algorithms


Chen; I. Kanj; and W. Jia.	2006	$O(1.2738^k+ kn)$	$O(\text{poly}(n))$
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
Chen; I. Kanj; and W. Jia.	2001	$O(kn + 1.2852^k)$	$O(k^3)$ auxiliary (potentially $O(k^2)$ )
Stege, Fellows + Interleaving method (Niedermeier, Rossmanith)	2000	O(kn+(1.2906)^k)	O(k^3) auxiliary (potentially O(k^2))
Niedermeier, Rossmanith	1999	$O(kn + 1.29175^k k^2)$	$O(k^3)$ auxiliary (potentially $O(k^2)$ )
Stege, Fellows	1999	O(kn+max((1.25542)^k k^2, (1.2906)^k k)	O(k^3) auxiliary (potentially O(k^2))
Downey	1998	$O(kn + 1.31951^k k^2)$	$O(k^3)$ auxiliary (potentially $O(k^2)$ )
Balasubramanian; Fellows	1996	$O(kn + 1.324718^k k^2)$	$O(k^3)$ auxiliary (potentially $O(k^2)$ )
Papadimitriou and M Yannakakis	1996	$O(3^k n)$	$O(k)$ auxiliary
Papadimitriou and M Yannakakis 1996 + Buss	1996	O(3^k k^2+kn)	O(k^2) auxiliary
Downey, Fellows	1995	O(kn+2^k k^2)	O(k^2) auxiliary
Sam Buss	1993	$O(kn + 2^k k^{2k + 2})$	$O(k^2)$
Brute force (backtracking search)	1940	$O(2^k n^{O(1)})$	$O(k)$
Exhaustive search	1940	O(m 2^n)	O(k) auxiliary

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Displaying 1 of 1 other relevant algorithms