Two Edge Modification Problems without Polynomial Kernels

DOI10.1007/978-3-642-11269-0_22zbMath1273.68181OpenAlexW1553479936MaRDI QIDQ3656868

Magnus Wahlström, Stefan Kratsch

Publication date: 14 January 2010

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

Full work available at URL: https://doi.org/10.1007/978-3-642-11269-0_22

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)

Related Items (22)

Parameterizing edge modification problems above lower bounds ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ Two edge modification problems without polynomial kernels ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Polynomial kernels for proper interval completion and related problems ⋮ Solving min ones 2-SAT as fast as vertex cover ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems ⋮ Kernel bounds for disjoint cycles and disjoint paths ⋮ Parameterized complexity of Eulerian deletion problems ⋮ A cubic-vertex kernel for flip consensus tree ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems ⋮ A polynomial kernel for trivially perfect editing ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ Polynomial Kernelization for Removing Induced Claws and Diamonds ⋮ Parameterized Complexity of Eulerian Deletion Problems ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some consequences of non-uniform conditions on uniform classes
• A more effective linear kernelization for cluster editing
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parameterized and exact computation. Second international workshop, IWPEC 2006, Zürich, Switzerland, September 13--15, 2006. Proceedings
• Algorithms and data structures. 10th international workshop, WADS 2007, Halifax, Canada, August 15--17, 2007. Proceedings.
• Parametrized complexity theory.
• NP-completeness results for edge modification problems
• The Approximability of Constraint Satisfaction Problems
• On Generating Triangle-Free Graphs
• On Problems without Polynomial Kernels (Extended Abstract)
• Kernelization Algorithms for d-Hitting Set Problems
• Kernelization and Complexity Results for Connectivity Augmentation Problems
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Fast FPT-Algorithms for Cleaning Grids
• Complexity classification of some edge modification problems

This page was built for publication: Two Edge Modification Problems without Polynomial Kernels