# Corelab Seminar

*2013-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.