On the hardness of losing width
DOI10.1007/978-3-642-28050-4_13zbMATH Open1352.68089OpenAlexW1423095052MaRDI QIDQ2891345FDOQ2891345
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
Recommendations
kernelization lower boundspolynomial parameter transformation\(\eta \)-transversalkernelization upper bounds
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)
Cites Work
- On problems without polynomial kernels
- Hitting forbidden minors: approximation and kernelization
- Incompressibility through Colors and IDs
- (Meta) Kernelization
- Bidimensionality and kernels
- Data reduction for graph coloring problems
- Cross-composition: a new technique for kernelization lower bounds
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Title not available (Why is that?)
- Title not available (Why is that?)
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)
