# Corelab Seminar2013-2014

### Prof. Vangelis Paschos (U. Paris-Dauphine) On the MAXIMUM MINIMAL VERTEX COVER problem

Abstract.
This talk addresses the MAXIMUM MINIMAL VERTEX COVER problem, which is the maximization version of the well studied INDEPENDENT DOMINATING SET problem, known to be NP-hard and highly inapproximable in polynomial time. Tight approximation results for this problem on general graphs are presented, namely, a polynomial time approximation algorithm that guarantees an $n^{-1/2}$ approximation ratio, while showing that unless P is not equal to NP, the problem is inapproximable within ratio $n^{\varepsilon-(1/2)}$ for any strictly positive $\varepsilon$. It is also shown that the problem is fixed-parameter tractable with respect to the size of an optimal solution and to the size of a maximum matching.