Two edge modification problems without polynomial kernels
DOI10.1016/J.DISOPT.2013.02.001zbMATH Open1506.68040OpenAlexW1998552318MaRDI QIDQ1662097FDOQ1662097
Stefan Kratsch, Magnus Wahlström
Publication date: 17 August 2018
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2013.02.001
Recommendations
- Two edge modification problems without polynomial kernels
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Incompressibility of \(H\)-free edge modification
- On Polynomial Kernelization of $$\mathcal {H}$$-free Edge Deletion
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Fixed-parameter tractability of graph modification problems for hereditary properties
- On problems without polynomial kernels
- Parametrized complexity theory.
- Title not available (Why is that?)
- Kernelization Lower Bounds by Cross-Composition
- Infeasibility of instance compression and succinct PCPs for NP
- Title not available (Why is that?)
- Complexity classification of some edge modification problems
- Kernel bounds for disjoint cycles and disjoint paths
- Some consequences of non-uniform conditions on uniform classes
- Title not available (Why is that?)
- NP-completeness results for edge modification problems
- A more effective linear kernelization for cluster editing
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Preprocessing of Min Ones Problems: A Dichotomy
- Kernelization Algorithms for d-Hitting Set Problems
- Two Edge Modification Problems without Polynomial Kernels
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- On generating triangle-free graphs
- Algorithms and data structures. 10th international workshop, WADS 2007, Halifax, Canada, August 15--17, 2007. Proceedings.
- Kernelization and Complexity Results for Connectivity Augmentation Problems
- Fast FPT-Algorithms for Cleaning Grids
Cited In (22)
- On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments
- Cutting a tree with subgraph complementation is hard, except for some small trees
- Title not available (Why is that?)
- 3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size
- Cutting a tree with subgraph complementation is hard, except for some small trees
- A Polynomial Kernel for Line Graph Deletion
- A Polynomial Kernel for Diamond-Free Editing
- Title not available (Why is that?)
- Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
- On the parameterized complexity of graph modification to first-order logic properties
- A survey of parameterized algorithms and the complexity of edge modification
- Parameterized aspects of strong subgraph closure
- Incompressibility of \(H\)-free edge modification problems
- A polynomial kernel for trivially perfect editing
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
- A completeness theory for polynomial (Turing) kernelization
- Exploring the subexponential complexity of completion problems
- Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
- A polynomial kernel for diamond-free editing
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- A Subexponential Parameterized Algorithm for Proper Interval Completion
This page was built for publication: Two edge modification problems without polynomial kernels
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662097)
