Vertex Coverage Problem

Introduction

At the moment, time polynomial algorithms for the exact solution of NP-hard problems are not known. Moreover, experts in the theory of complexity tend to the option that such algorithms do not exist. However, NP-hard tasks are often found in life. One of the ways 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.

A vertex covering is such a set of S vertices of the graph that each edge of the graph has at least one end of S.

The task is to choose in the undirected graph the minimum (by the number of vertices) vertex coverage.
')

Purpose.

We construct a simple algorithm for solving this problem, which is no more than two-fold mistaken. This means that if there is an optimal solution - a set of vertices T, then the solution S obtained by us satisfies the inequality | S | <= 2 | T | .

Example.

In the above example, the vertex cover is, for example, the set of vertices {0, 1, 2, 4} . All six vertices of the graph also form a vertex cover. However, the minimal vertex cover 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 a 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 .
• Remove from the graph all edges incident to the vertices u or v .

Repeat this step until we remove all edges of the graph.

An example of the algorithm.

In the example above, the minimum vertex coverage contains three vertices. For example, these may be vertices 1, 3, and 6 . Consider the work of our algorithm in the above example.

First iteration:

• Choose a random edge. For example, edge (1, 3) .
• Add to the solution S both vertices of the selected edge: S = {1, 3} .
• 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} .
• Remove from the graph all edges incident to vertices 4 or 6 .

There are no edges left in the graph. Consequently, the result of the operation of our algorithm is the vertex coverage S = {1, 3, 4, 6} .

Evidence.

Let us prove that the constructed set is a vertex cover. Indeed, at each 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 wrong no more than 2 times.

All edges e considered by the algorithm do not have common vertices. Consequently, 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 the famous work of Richard Karp “Reducibility among combinatorial problems” under the title Node Cover, the corresponding Vertex Cover problem is considered solvability and its NP-completeness is proved.
The algorithm we reviewed was independently developed by Fanica Gavril and Mihalis Yannakakis in 1974.
The best estimate of the approximate algorithm of the Vertex Cover problem for today owned by George Karakostas. Evaluation proved in the work of the vertex cover problem .

Conclusion

At the moment, there are no known polynomial approximation algorithms for Vertex Cover that significantly improve our accuracy. That is, it is not known algorithm of polynomial in time, which would be wrong no more than 1.999 times. Thus, we obtained a simple time-polynomial algorithm with good accuracy for solving an NP-hard problem.