On the hardness of losing width

DOI10.1007/978-3-642-28050-4_13MaRDI QIDQ2891345zbMATH OpenOpenAlexFDO

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

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On the hardness of losing width
• Kernelization for cycle transversal problems
• Kernelization for cycle transversal problems
• Inapproximability of \(H\)-transversal/packing
• Inapproximability of \(H\)-transversal/packing

Cites work

• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• scientific article; zbMATH DE number 6783432 (Why is no real title available?)
• (Meta) Kernelization
• Bidimensionality and kernels
• Cross-composition: a new technique for kernelization lower bounds
• Data reduction for graph coloring problems
• Hitting forbidden minors: approximation and kernelization
• Incompressibility through Colors and IDs
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• On problems without polynomial kernels
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Vertex cover kernelization revisited: upper and lower bounds for a refined parameter

Cited in

(5)

• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• On the hardness of losing width
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Strong hardness of approximation for tree transversals
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter

This page was built for publication: On the hardness of losing width

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