Dichotomy Results on the Hardness of $H$-free Edge Modification Problems

DOI10.1137/16M1055797zbMath1370.68225MaRDI QIDQ5346539

Naveen Sivadasan, R. B. Sandeep, N. R. Aravind

Publication date: 24 May 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-completeness\(H\)-free edge modificationparameterized lower bounds

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Destroying Bicolored $P_3$s by Deleting Few Edges ⋮ On subgraph complementation to \(H\)-free graphs ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ 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 ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy ⋮ A polynomial kernel for diamond-free editing ⋮ On subgraph complementation to \(H\)-free Graphs

Cites Work

• Unnamed Item
• Correlation clustering
• Cluster editing with locally bounded modifications
• Hardness of edge-modification problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Two edge modification problems without polynomial kernels
• Incompressibility of \(H\)-free edge modification problems
• Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems
• Exploring the Subexponential Complexity of Completion Problems
• Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems
• The complexity of some edge deletion problems
• Edge-Deletion Problems
• Tight Running Time Lower Bounds for Vertex Deletion Problems
• Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion
• Parameterized Algorithms

This page was built for publication: Dichotomy Results on the Hardness of $H$-free Edge Modification Problems