Packing cycles faster than Erdős-Pósa

DOI10.1137/17M1150037MaRDI QIDQ5232148zbMATHOpenAlexWikidataFDO

Authors Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh, Meirav Zehavi

Publication date 29 August 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.01037

zbMATH Keywords

graph algorithmsparameterized complexitycycle packingErdős-Pósa theorem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Approximation algorithms (68W25) Enumeration in graph theory (05C30) Paths and cycles (05C38)

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 ErdH{o}s-P'osa 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 non-uniform 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^{mathcalO(k^2)}cdot|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^{mathcalO(klo{g}^{2}k)}cdot|V|$-time (deterministic) algorithm using exponential space, which is a consequence of the ErdH{o}s-P'osa 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(klo{g}^{2}k)}cdot|V{|}^{mathcalO(1)}$, beating the bound $2^{mathcalO(klo{g}^{2}k)}cdot|V{|}^{mathcalO(1)}$, has been found. In light of this, it seems natural to ask whether the $2^{mathcalO(klo{g}^{2}k)}cdot|V{|}^{mathcalO(1)}$ bound is essentially optimal. In this paper, we answer this question negatively by developing a $2^{mathcalO(fracklo{g}^{2}kloglogk)}cdot|V|$-time (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 bound $2^{mathcalO(klo{g}^{2}k)}cdot|V{|}^{mathcalO(1)}$, our algorithm runs in time linear in $|V|$, and its space complexity is polynomial in the input size.

Recommendations

• Packing cycles faster than Erdős-Pósa
• The parameterized complexity of cycle packing: indifference is not an issue
• The parameterized complexity of cycle packing: indifference is not an issue
• Odd cycle packing
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing

Cites work

• scientific article; zbMATH DE number 6783430 (Why is no real title available?)
• A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
• Approximability of packing disjoint cycles
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Approximation algorithms and hardness results for cycle packing problems
• Bidimensionality and kernels
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Disjoint cycles intersecting a set of vertices
• Excluded grid theorem: improved and simplified
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• Finding a Minimum Circuit in a Graph
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Fundamentals of parameterized complexity
• Graph minors. V. Excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• Half-integral packing of odd cycles through prescribed vertices
• Highly parity linked graphs
• Kernel bounds for disjoint cycles and disjoint paths
• Kernel bounds for path and cycle problems
• Kernelization. Theory of parameterized preprocessing
• Large-treewidth graph decompositions and applications
• Lossy kernelization
• Mangoes and blueberries
• Non-zero disjoint cycles in highly connected group labelled graphs
• ON DISJOINT CYCLES
• On Independent Circuits Contained in a Graph
• On the complexity of \(k\)-SAT
• Packing cycles through prescribed vertices
• Packing directed cycles through a specified vertex set
• Parameterized Approximability of the Disjoint Cycle Problem
• Parameterized algorithms
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Parity linkage and the Erdős-Pósa property of odd cycles through prescribed vertices in highly connected graphs
• Partition into triangles on bounded degree graphs
• Polynomial bounds for the grid-minor theorem
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The Erdős-Pósa property for odd cycles in graphs of large connectivity
• The Erdős-Pósa property for odd cycles in highly connected graphs
• The Erdős-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces
• The Moore bound for irregular graphs

Cited in

(5)

• Packing cycles faster than Erdős-Pósa
• Kernelization of Arc Disjoint Cycle Packing in $$\alpha $$-Bounded Digraphs
• Kernelization of arc disjoint cycle packing in \(\alpha\)-bounded digraphs
• The parameterized complexity of cycle packing: indifference is not an issue
• The parameterized complexity of cycle packing: indifference is not an issue

This page was built for publication: Packing cycles faster than Erdős-Pósa

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232148)