Narayanaswamy, N.S. ;
Raman, Venkatesh ;
Ramanujan, M.S. ;
Saurabh, Saket
LP can be a cure for Parameterized Problems
Abstract
We investigate the parameterized complexity of Vertex Cover parameterized above the optimum value of the linear programming (LP) relaxation of the integer linear programming formulation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that even the most straightforward branching algorithm (after some preprocessing) results in an O^*(2.6181^r) algorithm for the problem where r is the excess of the
vertex cover size over the LP optimum. We write O^*(f(k)) for a time complexity of the form O(f(k)n^{O(1)}), where f(k) grows exponentially with k.
Then, using known and new reductions, we give O^*(2.6181^k) algorithms for the parameterized versions of Above Guarantee Vertex Cover, Odd Cycle Transversal, Split Vertex Deletion and Almost 2SAT, and an O^*(1.6181^k) algorithm for Konig Vertex Deletion, Vertex Cover Param by OCT and Vertex Cover Param by KVD. These algorithms significantly improve the best known bounds for these problems. The notable improvement is the bound for Odd Cycle Transversal for which this is the first major improvement after the first algorithm that showed it fixedparameter tractable in 2003. We also observe that using our algorithm, one can obtain a simple kernel for the classical vertex cover problem with at most 2kO(log k) vertices.
BibTeX  Entry
@InProceedings{narayanaswamy_et_al:LIPIcs:2012:3429,
author = {N.S. Narayanaswamy and Venkatesh Raman and M.S. Ramanujan and Saket Saurabh},
title = {{LP can be a cure for Parameterized Problems}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {338349},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3429},
URN = {urn:nbn:de:0030drops34291},
doi = {10.4230/LIPIcs.STACS.2012.338},
annote = {Keywords: Algorithms and data structures. Graph Algorithms, Parameterized Algorithms.}
}
2012
Keywords: 

Algorithms and data structures. Graph Algorithms, Parameterized Algorithms. 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Issue date: 

2012 
Date of publication: 

2012 