Lokshtanov, Daniel ;
Mouawad, Amer E. ;
Saurabh, Saket ;
Zehavi, Meirav
Packing Cycles Faster Than ErdosPosa
Abstract
The Cycle Packing problem asks whether a given undirected graph G=(V,E) contains k vertexdisjoint cycles. Since the publication of the classic ErdosPosa theorem in 1965, this problem received significant scientific attention in the fields of Graph Theory and Algorithm Design. In particular, this problem is one of the first problems studied in the framework of Parameterized Complexity. The nonuniform fixedparameter tractability of Cycle Packing follows from the Robertson–Seymour theorem, a fact already observed by Fellows and Langston in the 1980s. In 1994, Bodlaender showed that Cycle Packing can be solved in time 2^{O(k^2)}V using exponential space. In case a solution exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a 2^{O(k\log^2 k)}Vtime (deterministic) algorithm using exponential space, which is a consequence of the ErdosPosa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on Parameterized Complexity. Yet, no algorithm that runs in time 2^{o(k\log^2k)}V^{O(1)}, beating the bound 2^{O(k\log^2k)}\cdot V^{O(1)}, has been found. In light of this, it seems natural to ask whether the 2^{O(k\log^2k)}V^{O(1)}$ bound is essentially optimal. In this paper, we answer this question negatively by developing a 2^{O(k\log^2k/log log k})} Vtime (deterministic) algorithm for Cycle Packing. In case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the known bound, our algorithm runs in time linear in V, and its space complexity is polynomial in the input size.
BibTeX  Entry
@InProceedings{lokshtanov_et_al:LIPIcs:2017:7385,
author = {Daniel Lokshtanov and Amer E. Mouawad and Saket Saurabh and Meirav Zehavi},
title = {{Packing Cycles Faster Than ErdosPosa}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {71:171:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7385},
URN = {urn:nbn:de:0030drops73857},
doi = {10.4230/LIPIcs.ICALP.2017.71},
annote = {Keywords: Parameterized Complexity, Graph Algorithms, Cycle Packing, Erd{\"o}sP{\'o}sa Theorem}
}
2017
Keywords: 

Parameterized Complexity, Graph Algorithms, Cycle Packing, ErdösPósa Theorem 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

2017 