Packing cycles faster than Erdős-Pósa

DOI10.1137/17M1150037zbMATH Open1419.05202arXiv1707.01037OpenAlexW2955871520WikidataQ127597022 ScholiaQ127597022MaRDI QIDQ5232148FDOQ5232148

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

Publication date: 29 August 2019

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

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.

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

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

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)

Cites Work

• Fundamentals of parameterized complexity
• Graph minors. XIII: The disjoint paths problem
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Non-zero disjoint cycles in highly connected group labelled graphs
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• ON DISJOINT CYCLES
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms
• On the complexity of \(k\)-SAT
• Graph minors. V. Excluding a planar graph
• Mangoes and blueberries
• Approximation algorithms and hardness results for cycle packing problems
• On Independent Circuits Contained in a Graph
• Bidimensionality and Geometric Graphs
• Highly parity linked graphs
• Large-treewidth graph decompositions and applications
• Finding a Minimum Circuit in a Graph
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Kernel bounds for disjoint cycles and disjoint paths
• Half-integral packing of odd cycles through prescribed vertices
• Packing cycles through prescribed vertices
• Excluded Grid Theorem
• The Moore bound for irregular graphs
• Title not available (Why is that?)
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• The Erdős-Pósa property for odd cycles in graphs of large connectivity
• Kernel bounds for path and cycle problems
• Approximability of packing disjoint cycles
• Parity Linkage and the Erdős-Pósa Property of Odd Cycles Through Prescribed Vertices in Highly Connected Graphs
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Disjoint cycles intersecting a set of vertices
• Parameterized Approximability of the Disjoint Cycle Problem
• A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
• 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
• Kernelization
• Lossy kernelization
• Packing directed cycles through a specified vertex set
• Partition into triangles on bounded degree graphs
• Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
• Polynomial Bounds for the Grid-Minor Theorem

Cited In (2)

• Kernelization of arc disjoint cycle packing in \(\alpha\)-bounded digraphs
• Kernelization of Arc Disjoint Cycle Packing in $$\alpha $$-Bounded Digraphs

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)