• norsk
    • English
  • English 
    • norsk
    • English
  • Login
View Item 
  •   Home
  • University of Bergen Library
  • Registrations from Cristin
  • View Item
  •   Home
  • University of Bergen Library
  • Registrations from Cristin
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Packing cycles faster than Erdos-Posa

Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket; Zehavi, Meirav
Journal article, Peer reviewed
Published version
Thumbnail
View/Open
PDF (451.9Kb)
URI
https://hdl.handle.net/11250/2722601
Date
2019
Metadata
Show full item record
Collections
  • Department of Informatics [536]
  • Registrations from Cristin [65]
Original version
SIAM Journal on Discrete Mathematics. 2019, 33 (3), 1194-1215.   10.1137/17M1150037
Abstract
The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertex-disjoint cycles. Since the publication of the classic Erdös--Pósa theorem in 1965, this problem received significant 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 fixed-parameter 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^{\mathcal{O}(k^2)}\cdot |V|$ using exponential space. In the 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^{\mathcal{O}(k\log^2k)}\cdot |V|$-time (deterministic) algorithm using exponential space, which is a consequence of the Erdös--Pósa 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)}\cdot |V|^{\mathcal{O}(1)}$, beating the bound $2^{\mathcal{O}(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$, has been found. In light of this, it seems natural to ask whetherthe $2^{\mathcal{O}(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$ bound is essentially optimal. In this paper, we answer this question negatively by developing a $2^{\mathcal{O}(\frac{k\log^2k}{\log\log k})}\cdot |V|$-time (deterministic) algorithm for Cycle Packing. In the case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the bound $2^{\mathcal{O}(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$, our algorithm runs in time linear in $|V|$, and its space complexity is polynomial in the input size.
Publisher
SIAM
Journal
SIAM Journal on Discrete Mathematics
Copyright
Copyright 2019, Society for Industrial and Applied Mathematics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit
 

 

Browse

ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDocument TypesJournalsThis CollectionBy Issue DateAuthorsTitlesSubjectsDocument TypesJournals

My Account

Login

Statistics

View Usage Statistics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit