Vertex cover
It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP.
It is a typical example of an NP-hard optimization problem that has an approximation algorithm.
The minimum vertex cover problem can be formulated as a half-integral, linear program whose dual linear program is the maximum matching problem.
The lower figure shows examples of minimum vertex covers in the previous graphs.
The minimum vertex cover problem is the optimization problem of finding a smallest vertex cover in a given graph.
It is often used in computational complexity theory as a starting point for NP-hardness proofs.
The (weighted) minimum vertex cover problem can be formulated as the following integer linear program (ILP).
approximation algorithm for the minimum vertex cover problem.
Furthermore, the linear programming relaxation of that ILP is half-integral, that is, there exists an optimal solution for which each entry
A 2-approximate vertex cover can be obtained from this fractional solution by selecting the subset of vertices whose variables are nonzero.
The decision variant of the vertex cover problem is NP-complete, which means it is unlikely that there is an efficient algorithm to solve it exactly for arbitrary graphs.
[4] For bipartite graphs, the equivalence between vertex cover and maximum matching described by Kőnig's theorem allows the bipartite vertex cover problem to be solved in polynomial time.
For tree graphs, an algorithm finds a minimal vertex cover in polynomial time by finding the first leaf in the tree and adding its parent to the minimal vertex cover, then deleting the leaf and parent and all associated edges and continuing repeatedly until no edges remain in the tree.
An exhaustive search algorithm can solve the problem in time 2knO(1), where k is the size of the vertex cover.
Vertex cover is therefore fixed-parameter tractable, and if we are only interested in small k, we can solve the problem in polynomial time.
One algorithmic technique that works here is called bounded search tree algorithm, and its idea is to repeatedly choose some vertex and recursively branch, with two cases at each step: place either the current vertex or all its neighbours into the vertex cover.
The algorithm for solving vertex cover that achieves the best asymptotic dependence on the parameter runs in time
[6] This algorithm is again optimal, in the sense that, under the exponential time hypothesis, no algorithm can solve vertex cover on planar graphs in time
[7] One can find a factor-2 approximation by repeatedly taking both endpoints of an edge into the vertex cover, then removing them from the graph.
Put otherwise, we find a maximal matching M with a greedy algorithm and construct a vertex cover C that consists of all endpoints of the edges in M. In the following figure, a maximal matching M is marked with red, and the vertex cover C is marked with blue.
The set C constructed this way is a vertex cover: suppose that an edge e is not covered by C; then M ∪ {e} is a matching and e ∉ M, which is a contradiction with the assumption that M is maximal.
That is, an optimal cover contains at least one endpoint of each edge in M; in total, the set C is at most 2 times as large as the optimal vertex cover.
This simple algorithm was discovered independently by Fanica Gavril and Mihalis Yannakakis.
The minimum vertex cover problem is APX-complete, that is, it cannot be approximated arbitrarily well unless P = NP.
Using techniques from the PCP theorem, Dinur and Safra proved in 2005 that minimum vertex cover cannot be approximated within a factor of 1.3606 for any sufficiently large vertex degree unless P = NP.
[12] Moreover, if the unique games conjecture is true then minimum vertex cover cannot be approximated within any constant factor better than 2.
[13] Although finding the minimum-size vertex cover is equivalent to finding the maximum-size independent set, as described above, the two problems are not equivalent in an approximation-preserving way: The Independent Set problem has no constant-factor approximation unless P = NP.
Approximation algorithm:[14][15] Vertex cover optimization serves as a model for many real-world and theoretical problems.
For example, a commercial establishment interested in installing the fewest possible closed circuit cameras covering all hallways (edges) connecting all rooms (nodes) on a floor might model the objective as a vertex cover minimization problem.
The problem has also been used to model the elimination of repetitive DNA sequences for synthetic biology and metabolic engineering applications.
