Choose Outsiders First: a mean 2-approximation random algorithm for covering problems. ∗

A high number of discrete optimization problems, including Vertex Cover, Set Cover or Feedback Vertex Set, can be unified into the class of covering problems. Several of them were shown to be inapproximable by deterministic algorithms. This article proposes a new random approach, called Choose Outsiders First, which consists in selecting randomly ele-ments which are excluded from the cover. We show that this approach leads to random outputs which mean size is at most twice the optimal solution. In his landmark paper in complexity theory [11], R. Karp provides a list of 21 NP-complete problems from which most of the NP-completness results are deduced. Among them are the extensively studied Vertex Cover, Set Cover, Feedback Vertex (or Arc) Set or Hitting Set problems, which belong to the class of covering problems. Covering problems ask how large a certain combinatorial structure has to be to cover another one, and have a wide range of applications in all areas involving combinatorial optimization problems, including VLSI systems [10], routing [6] or scheduling [7]. In the last decades, they also became central in computational biology [12] as parsimony is often considered as the choice criteria between the different evolutional scenarios explaining the observations [9]. Most of the covering problems are NP-complete, so that they need to be solved by using heuristics. The proposed algorithms can mainly be classified into two families. The firt one consists in the primal-dual approaches which are based on the formulation of covering problems as integer linear programming problems [13]. The second type of approximation algorithms are based on local ratio techniques which consist in solving a problem locally and extending the ∗This work was supported by the ERC Advanced Grant SISYPHE. 1 a