Abstract (EN)

We address the max min vertex cover problem, which is the maximization version of the well studied MIN INDEPENDENT DOMINATING SET problem, known to be NP-hard and highly inapproximable in polynomial time. We present tight approximation results for this problem on general graphs, namely a polynomial approximation algorithm which guarantees an $n^{−1/2}$ approximation ratio, while showing that unless P = NP, the problem is inapproximable within ratio $n^{ε-(1/2)}$ for any strictly positive. We also analyze the problem on various restricted classes of graph, on which we show polynomiality or constant-approximability of the problem. Finally, we show that the problem is fixed-parameter tractable with respect to the size of an optimal solution, to tree-width and to the size of a maximum matching.