MAXIMUM MINIMAL VERTEX COVER PARAMETERIZED BY VERTEX COVER

摘要

The parameterized complexity of problems is often studied with respect to the size of their optimal solutions. However, for a maximization problem, the size of the optimal solution can be very large, rendering algorithms parameterized by it inefficient. Therefore, we suggest studying the parameterized complexity of maximization problems with respect to the size of the optimal solutions to their minimization versions. We examine this suggestion by considering the Maximum Minimal Vertex Cover (MMVC) problem, which has applications to wireless ad hoc networks and whose minimization version, Vertex Cover, is one of the most studied problems in the field of parameterized complexity. We first present tight conditional lower bounds for the running time of any algorithm for MMVC or its weighted variant. Next, we develop a parameterized approximation algorithm for MMVC and its weighted variant. The approximation ratio of this algorithm cannot be achieved by polynomial-time algorithms unless P = NP, and its running time cannot be matched by exact parameterized algorithms unless the strong exponential time hypothesis fails. In particular, the algorithm de fines a user-controlled parameter that corresponds to a trade-off between time and approximation ratio.