文章基本信息

标题：Subexponential Parameterized Odd Cycle Transversal on Planar Graphs
本地全文：下载
作者：Daniel Lokshtanov ; Saket Saurabh ; Magnus Wahlstr{\"o}m 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：18
页码：424-434
DOI：10.4230/LIPIcs.FSTTCS.2012.424
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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].
关键词：Graph Theory; Parameterized Algorithms; Odd Cycle Transversal