2026-07-20T11:02:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3878 2024-03-06T10:34:34Z ddc:004 open_access

Subexponential Parameterized Odd Cycle Transversal on Planar Graphs Lokshtanov, Daniel Saurabh, Saket Wahlström, Magnus Graph Theory Parameterized Algorithms Odd Cycle Transversal 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Lokshtanov and Saket Saurabh and Magnus Wahlström 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.424 urn:nbn:de:0030-drops-38783 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.424 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode