2026-07-22T16:11:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17309 2024-03-06T10:59:25Z ddc:004 open_access

Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy Belova, Tatiana Bliznets, Ivan Parameterized complexity Hardness of approximation Edge modification problems For a fixed graph H, the H-free Edge Deletion/Completion/Editing problem asks to delete/add/edit the minimum possible number of edges in G to get a graph that does not contain an induced subgraph isomorphic to the graph H. In this work, we investigate H-free Edge Deletion/Completion/Editing problems in terms of the hardness of their approximation. We formulate a conjecture according to which all the graphs with at least five vertices can be classified into several groups of graphs with specific structural properties depending on the hardness of approximation for the corresponding H-free Edge Deletion/Completion/Editing problems. Also, we make significant progress in proving that conjecture by showing that it is sufficient to resolve it only for a finite set of graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tatiana Belova and Ivan Bliznets 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.24 urn:nbn:de:0030-drops-173097 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.24 eng https://creativecommons.org/licenses/by/4.0/legalcode