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: https://drops.dagstuhl.de/opus/volltexte/2012/3878/
Lokshtanov, Daniel ; Saurabh, Saket ; Wahlström, Magnus
Subexponential Parameterized Odd Cycle Transversal on Planar Graphs
| pdf-format: |
|
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 | |
| Seminar: | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) | |
| Issue date: | 2012 | |
| Date of publication: | 14.12.2012 |
