Vertex Cover Problem Parameterized Above and Below Tight Bounds

2009/07/26 by Gregory Gutin, Gutin, Gregory, Eun Jung Kim +5
Computer Science · Engineering · #Advanced Graph Theory Research #graph theory and CDMA systems #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.0907.4488

Abstract

We study the well-known Vertex Cover problem parameterized above and below tight bounds. We show that two of the parameterizations (both were suggested by Mahajan, Raman and Sikdar, J. Computer and System Sciences, 75(2):137--153, 2009) are fixed-parameter tractable and two other parameterizations are W[1]-hard (one of them is, in fact, W[2]-hard).

Related

• Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee
• Vertex Cover and Feedback Vertex Set Above and Below Structural\n Guarantees
• A faster algorithm for Vertex Cover parameterized by solution size
• A Fixed Parameter Tractable Approach for Solving the Vertex Cover Problem in Polynomial Time Complexity
• Faster Parameterized Algorithms using Linear Programming