Hardness of Approximation for H -free Edge Modification Problems

DOI10.1145/3196834zbMath1427.68105OpenAlexW2963777460MaRDI QIDQ4973877

Paweł Komosa, Marek Cygan, Michał Pilipczuk, Ivan A. Bliznets

Publication date: 6 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3196834

zbMATH Keywords

hardness of approximationfixed-parameter tractabilityexponential time hypothesisgraph modification problems\(H\)-free graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (3)

A survey of parameterized algorithms and the complexity of edge modification ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ A polynomial kernel for diamond-free editing

This page was built for publication: Hardness of Approximation for H -free Edge Modification Problems