Definition
Vertex Cover Problem
Let
be a graph and , whereby is part of the input (not a constant). The vertex cover problem is a decision problem asking whether there exists a vertex cover of , such that . The following holds:
Relation to Independent Set
Let
Equivalence to Independent Set Problem
The vertex cover problem is equivalent (w.r.t. polynomial time reduction) to the independent set problem.
Let
be an instance of the vertex cover problem and be the number of vertices of . In polynomial time, we generate
, an instance of the independent set problem. The reduction is correct since has a vertex cover if is an independent set of size . Trivially, the reduction is polynomial, since we only replaced
by .
Approaches
Brute-force
Brute-force
A brute-force approach tests all
subsets of size and requires time to test whether a subset is a vertex cover.
Recursive
