Kernelization of cycle packing with relaxed disjointness constraints

DOI10.1137/17M1136614zbMATH Open1397.68088OpenAlexW2884495246WikidataQ129561045 ScholiaQ129561045MaRDI QIDQ3174716FDOQ3174716

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

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

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)

Cites Work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On problems without polynomial kernels
• Parametrized complexity theory.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Kernelization – Preprocessing with a Guarantee
• A 4 k ² kernel for feedback vertex set
• Title not available (Why is that?)
• Title not available (Why is that?)
• Parameterized Algorithms
• Title not available (Why is that?)
• On Independent Circuits Contained in a Graph
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Infeasibility of instance compression and succinct PCPs for NP
• New Limits to Classical and Quantum Instance Compression
• Kernel bounds for disjoint cycles and disjoint paths
• Title not available (Why is that?)
• Title not available (Why is that?)
• Kernelization Algorithms for Packing Problems Allowing Overlaps
• Logic, graphs, and algorithms
• The \((n^ 2-1)\)-puzzle and related relocation problems
• On r-Simple k-Path
• A completeness theory for polynomial (Turing) kernelization
• A Parameterized Algorithm for Packing Overlapping Subgraphs
• The ${\mathcal{G}}$ -Packing with t-Overlap Problem
• Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints
• Polynomial-delay enumeration of monotonic graph classes

Cited In (1)

• Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths

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)