Kernelization of cycle packing with relaxed disjointness constraints

DOI10.1137/17M1136614MaRDI QIDQ3174716zbMATH OpenOpenAlexWikidataFDO

Authors Akanksha Agrawal, Daniel Lokshtanov, Diptapriyo Majumdar, Amer E. Mouawad, Saket Saurabh

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

zbMATH Keywords

lower boundsparameterized complexityrelaxationkernelizationcycle packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Kernelization of cycle packing with relaxed disjointness constraints
• Planar vertex-disjoint cycle packing: new structures and improved kernel
• Edge-disjoint packing of stars and cycles
• Edge-disjoint packing of stars and cycles
• Kernel bounds for disjoint cycles and disjoint paths

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• scientific article; zbMATH DE number 7053262 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A 4k^2 kernel for feedback vertex set
• A completeness theory for polynomial (Turing) kernelization
• A parameterized algorithm for packing overlapping subgraphs
• Fast algorithms for parameterized problems with relaxed disjointness constraints
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• Kernelization -- preprocessing with a guarantee
• Kernelization algorithms for packing problems allowing overlaps
• Kernelization of cycle packing with relaxed disjointness constraints
• Kernelization of packing problems
• Logic, graphs, and algorithms
• New limits to classical and quantum instance compression
• On Independent Circuits Contained in a Graph
• On problems without polynomial kernels
• On r-Simple k-Path
• Parameterized algorithms
• Parametrized complexity theory.
• Polynomial-delay enumeration of monotonic graph classes
• Recent developments in kernelization: a survey
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• The \((n^ 2-1)\)-puzzle and related relocation problems
• The \({\mathcal{G}}\)-packing with \(t\)-overlap problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(2)

• Linear-vertex kernel for the problem of packing r-stars into a graph without long induced paths
• Kernelization of cycle packing with relaxed disjointness constraints

This page was built for publication: Kernelization of cycle packing with relaxed disjointness constraints

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