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

Lokshtanov, Daniel ; Saurabh, Saket ; Wahlström, Magnus

Subexponential Parameterized Odd Cycle Transversal on Planar Graphs

pdf-format:
39.pdf (0.5 MB)

Abstract

In the Odd Cycle Transversal (OCT) problem we are given a graph G on n vertices and an integer k, the objective is to determine whether there exists a vertex set O in G of size at most k such that G - O is bipartite. Reed, Smith and Vetta [Oper. Res. Lett., 2004] gave an algorithm for OCT with running time 3^kn^{O(1)}. Assuming the exponential time hypothesis of Impagliazzo, Paturi and Zane, the running time can not be improved to 2^{o(k)}n^{O(1)}. We show that OCT admits a randomized algorithm running in O(n^{O(1)} + 2^{O(sqrt{k} log k)}n) time when the input graph is planar. As a byproduct we also obtain a linear time algorithm for OCT on planar graphs with running time O(n^O(1) + 2O( sqrt(k) log k) n) time. This improves over an algorithm of Fiorini et al. [Disc. Appl. Math., 2008].

BibTeX - Entry

@InProceedings{lokshtanov_et_al:LIPIcs:2012:3878,
  author =	{Daniel Lokshtanov and Saket Saurabh and Magnus Wahlstr{\"o}m},
  title =	{{Subexponential Parameterized Odd Cycle Transversal on Planar Graphs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
  pages =	{424--434},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2012/3878},
  URN =		{urn:nbn:de:0030-drops-38783},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.424},
  annote =	{Keywords: Graph Theory, Parameterized Algorithms, Odd Cycle Transversal}
}

Keywords: Graph Theory, Parameterized Algorithms, Odd Cycle Transversal
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Issue Date: 2012
Date of publication: 14.12.2012

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