Kernelization of Cycle Packing with Relaxed Disjointness Constraints

DOI10.1137/17M1136614zbMath1397.68088MaRDI QIDQ3174716

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

Publication date: 18 July 2018

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

zbMATH Keywords

relaxation; lower bounds; parameterized complexity; kernelization; cycle packing

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)