Kernelization of Cycle Packing with Relaxed Disjointness Constraints
DOI10.1137/17M1136614zbMath1397.68088OpenAlexW2884495246WikidataQ129561045 ScholiaQ129561045MaRDI QIDQ3174716
Amer E. Mouawad, Akanksha Agrawal, Saket Saurabh, Diptapriyo Majumdar, Daniel Lokshtanov
Publication date: 18 July 2018
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/17m1136614
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- The \((n^ 2-1)\)-puzzle and related relocation problems
- On problems without polynomial kernels
- A completeness theory for polynomial (Turing) kernelization
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Kernelization – Preprocessing with a Guarantee
- On r-Simple k-Path
- A 4 k 2 kernel for feedback vertex set
- Kernelization Algorithms for Packing Problems Allowing Overlaps
- New Limits to Classical and Quantum Instance Compression
- Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints
- A Parameterized Algorithm for Packing Overlapping Subgraphs
- On Independent Circuits Contained in a Graph
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- The ${\mathcal{G}}$ -Packing with t-Overlap Problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
