Vertex coverage problem
Introduction
At present, polynomial-time algorithms for the exact solution of NP-hard problems are not known. Moreover, specialists in complexity theory are inclined to the option that such algorithms do not exist. However, NP-hard tasks are often found in life. One way to deal with NP-hard problems in practice is to use approximate algorithms.
Consider the best known approximate algorithm for solving the vertex coverage problem .
Formulation of the problem.
Vertex cover - is a set S of vertices that each edge of at least one end part of the S .
The task is to select the minimum (in terms of the number of vertices) vertex coverage in an undirected graph.
Goal.
Let us construct a simple algorithm for solving this problem, which is mistaken no more than twice. This means that if there is an optimal solution - the set of vertices T, then the solution S obtained by us satisfies the inequality | S | <= 2 | T | .
Example.
In the above example, the vertex covering is, for example, the set of vertices {0, 1, 2, 4} . All six vertices of the graph also form a vertex cover. However, the minimum vertex coverage in the graph under consideration will be a set consisting of only two vertices. For example, these can be vertices with numbers 1 and 3. Indeed, all edges of the graph are covered by these two vertices.
Algorithm.
At each step of the algorithm, we perform the following actions:
- Choose a random edge of the graph e = (u, v) .
- Add to the solution S both selected vertices u and v .
- We remove from the graph all edges incident to the vertices u or v .
Repeat this step until we delete all edges of the graph.
An example of the algorithm.
In the above example, the minimum vertex coverage contains three vertices. For example, these may be peaks 1, 3, and 6 . Consider the operation of our algorithm in the above example.
First iteration:
- Choose a random edge. For example, an edge (1, 3) .
- Add to the solution S both vertices of the selected edge: S = {1, 3} .
- We remove from the graph all edges incident to vertices 1 or 3 .
Second iteration:
- Choose a random edge. Let it be an edge (4, 6) .
- Add to the solution S both vertices of the selected edge: S = {1, 3, 4, 6} .
- We remove from the graph all edges incident to vertices 4 or 6 .
There are no edges in the graph. Therefore, the result of the work of our algorithm will be a vertex cover S = {1, 3, 4, 6} .
Evidence.
Let us prove that the constructed set is a vertex covering. Indeed, at every step we removed only the already covered ribs. We repeated this iteration while there were still edges in the graph. Thus, we covered all the edges of the graph.
Let us prove that our algorithm is no more than 2 times erroneous.
All edges e considered by the algorithm have no common vertices. Therefore, from each of these edges, the optimal solution T must include at least one vertex. This means that 2 | T |> = | S | .
A bit of history
In Richard Karp 's famous work “Reducibility among combinatorial problems” called Node Cover, the Vertex Cover problem is considered to be solvable and its NP-completeness is proved.
The algorithm we examined was independently developed by Fanica Gavril and Mihalis Yannakakis in 1974.
The best known to date estimate of the approximate algorithm of the Vertex Cover problem
belongs to George Karakostas. Estimation is proved in A better approximation ratio for the vertex cover problem .Conclusion
At present, there are no known polynomial approximate algorithms for Vertex Cover that significantly improve our accuracy. That is, it is not known an algorithm polynomial in time, which would be mistaken no more than 1.999 times. Thus, we obtained a simple polynomial-time algorithm with good accuracy for solving an NP-hard problem.