Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
From MaRDI portal
Publication:2071824
DOI10.1016/j.jcss.2021.11.001OpenAlexW3216018497MaRDI QIDQ2071824
Publication date: 31 January 2022
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.11761
Related Items
On subgraph complementation to \(H\)-free graphs, Completion to chordal distance-hereditary graphs: a quartic vertex-kernel, Cutting a tree with subgraph complementation is hard, except for some small trees, A cubic vertex-kernel for \textsc{Trivially Perfect Editing}, On subgraph complementation to \(H\)-free Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Chordal editing is fixed-parameter tractable
- Claw-free graphs. VI: Colouring
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Claw-free graphs. III: Circular interval graphs
- Claw-free graphs. IV: Decomposition theorem
- Claw-free graphs. V. Global structure
- The node-deletion problem for hereditary properties is NP-complete
- The splittance of a graph
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Two edge modification problems without polynomial kernels
- On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
- Cluster editing: kernelization based on edge cuts
- Claw-free graphs. VII. Quasi-line graphs
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Incompressibility of \(H\)-free edge modification problems
- Claw-free graphs. I: Orientable prismatic graphs
- Polynomial kernelization for removing induced claws and diamonds
- Claw-free graphs. II: Non-orientable prismatic graphs
- Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems
- Edge-Deletion Problems
- Node-Deletion Problems on Bipartite Graphs
- Kernelization
- A Polynomial Kernel for Diamond-Free Editing
- Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
- Parameterized Algorithms
- Polynomial kernels for paw-free edge modification problems
- Complexity classification of some edge modification problems
- A survey of parameterized algorithms and the complexity of edge modification
