License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.338
URN: urn:nbn:de:0030-drops-34291
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3429/
Go to the corresponding LIPIcs Volume Portal

Narayanaswamy, N.S. ; Raman, Venkatesh ; Ramanujan, M.S. ; Saurabh, Saket

LP can be a cure for Parameterized Problems

pdf-format:
45.pdf (0.6 MB)

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 2-SAT, 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 fixed-parameter 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 2k-O(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 =	{338--349},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3429},
  URN =		{urn:nbn:de:0030-drops-34291},
  doi =		{10.4230/LIPIcs.STACS.2012.338},
  annote =	{Keywords: Algorithms and data structures. Graph Algorithms, Parameterized Algorithms.}
}

Keywords: Algorithms and data structures. Graph Algorithms, Parameterized Algorithms.
Collection: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI