On the Hardness of Losing Width

DOI10.1007/978-3-642-28050-4_13zbMath1352.68089OpenAlexW1423095052MaRDI QIDQ2891345

Marek Cygan, Marcin Pilipczuk, Saket Saurabh, Daniel Lokshtanov, Michał Pilipczuk

Publication date: 15 June 2012

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-28050-4_13

zbMATH Keywords

kernelization lower boundspolynomial parameter transformation\(\eta \)-transversalkernelization upper bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Related Items

Uniform Kernelization Complexity of Hitting Forbidden Minors, Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, Preprocessing subgraph and minor problems: when does a small vertex cover help?

Cites Work

• On problems without polynomial kernels
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Data Reduction for Graph Coloring Problems
• Incompressibility through Colors and IDs
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• (Meta) Kernelization
• Bidimensionality and Geometric Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item