On the max min vertex cover problem ?
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 graphs, 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 treewidth and to the size of a maximum matching.
max min vertex cover min independent dominating set inapproximability polynomial approximation parametric complexity