2 Search Results for "Ramanujan, M.S."

Document
Brief Announcement
DOI: 10.4230/LIPIcs.ICALP.2018.110
Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS

Authors: Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Roohani Sharma, and Meirav Zehavi

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In the Directed Feedback Vertex Set (DFVS) problem, we are given as input a directed graph D and an integer k, and the objective is to check whether there exists a set S of at most k vertices such that F=D-S is a directed acyclic graph (DAG). Determining whether DFVS admits a polynomial kernel (parameterized by the solution size) is one of the most important open problems in parameterized complexity. In this article, we give a polynomial kernel for DFVS parameterized by the solution size plus the size of any treewidth-eta modulator, for any positive integer eta. We also give a polynomial kernel for the problem, which we call Vertex Deletion to treewidth-eta DAG, where given as input a directed graph D and a positive integer k, the objective is to decide whether there exists a set of at most k vertices, say S, such that D-S is a DAG and the treewidth of D-S is at most eta.
Cite as

Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 110:1-110:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lokshtanov_et_al:LIPIcs.ICALP.2018.110,
  author =	{Lokshtanov, Daniel and Ramanujan, M. S. and Saurabh, Saket and Sharma, Roohani and Zehavi, Meirav},
  title =	{{Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{110:1--110:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.110},
  URN =		{urn:nbn:de:0030-drops-91146},
  doi =		{10.4230/LIPIcs.ICALP.2018.110},
  annote =	{Keywords: Polynomial Kernel, Directed Feedback Vertex Set, Treewidth Modulator}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.338
LP can be a cure for Parameterized Problems

Authors: N.S. Narayanaswamy, Venkatesh Raman, M.S. Ramanujan, and Saket Saurabh

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

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.
Cite as

N.S. Narayanaswamy, Venkatesh Raman, M.S. Ramanujan, and Saket Saurabh. LP can be a cure for Parameterized Problems. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 338-349, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{narayanaswamy_et_al:LIPIcs.STACS.2012.338,
  author =	{Narayanaswamy, N.S. and Raman, Venkatesh and Ramanujan, M.S. and Saurabh, Saket},
  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 =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.338},
  URN =		{urn:nbn:de:0030-drops-34291},
  doi =		{10.4230/LIPIcs.STACS.2012.338},
  annote =	{Keywords: Algorithms and data structures. Graph Algorithms, Parameterized Algorithms.}
}
  • Refine by Author
  • 2 Saurabh, Saket
  • 1 Lokshtanov, Daniel
  • 1 Narayanaswamy, N.S.
  • 1 Raman, Venkatesh
  • 1 Ramanujan, M. S.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Fixed parameter tractability

  • Refine by Keyword
  • 1 Algorithms and data structures. Graph Algorithms
  • 1 Directed Feedback Vertex Set
  • 1 Parameterized Algorithms.
  • 1 Polynomial Kernel
  • 1 Treewidth Modulator

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2012
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact