Incompressibility of \(H\)-free edge modification problems
From MaRDI portal
Publication:2343091
DOI10.1007/s00453-014-9937-xzbMath1312.68096OpenAlexW2155453078MaRDI QIDQ2343091
Publication date: 4 May 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-014-9937-x
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (25)
Parameterizing edge modification problems above lower bounds ⋮ Finding Two Edge-Disjoint Paths with Length Constraints ⋮ Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ Kernel for \(K_t\)\textsc{-free Edge Deletion} ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Parameterized aspects of strong subgraph closure ⋮ On subgraph complementation to \(H\)-free graphs ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ Dichotomy Results on the Hardness of $H$-free Edge Modification Problems ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ Unnamed Item ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ Unnamed Item ⋮ A Polynomial Kernel for Line Graph Deletion ⋮ A Polynomial Kernel for Diamond-Free Editing ⋮ A polynomial kernel for trivially perfect editing ⋮ Unnamed Item ⋮ On the parameterized complexity of graph modification to first-order logic properties ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy ⋮ A polynomial kernel for diamond-free editing ⋮ Two edge-disjoint paths with length constraints ⋮ On subgraph complementation to \(H\)-free Graphs
Cites Work
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Graph-modeled data clustering: Exact algorithms for clique generation
- On problems without polynomial kernels
- Some simplified NP-complete graph problems
- Strong normalization for non-structural subtyping via saturated sets
- Two edge modification problems without polynomial kernels
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Incompressibility of H-Free Edge Modification
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Kernelization Lower Bounds by Cross-Composition
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
This page was built for publication: Incompressibility of \(H\)-free edge modification problems
