2026-07-20T11:15:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24475 2025-12-16T13:59:36Z ddc:004 open_access

Graph Modification of Bounded Size to Minor-Closed Classes as Fast as Vertex Deletion Morelle, Laure Sau, Ignasi Thilikos, Dimitrios M. Graph modification problems Parameterized complexity Graph minors Flat Wall theorem Irrelevant vertex technique Algorithmic meta-theorem Parametric dependence Dynamic programming A replacement action is a function ℒ that maps each graph H to a collection of graphs of size at most |V(H)|. Given a graph class ℋ, we consider a general family of graph modification problems, called ℒ-Replacement to ℋ, where the input is a graph G and the question is whether it is possible to replace some induced subgraph H₁ of G on at most k vertices by a graph H₂ in ℒ(H₁) so that the resulting graph belongs to ℋ. ℒ-Replacement to ℋ can simulate many graph modification problems including vertex deletion, edge deletion/addition/edition/contraction, vertex identification, subgraph complementation, independent set deletion, (induced) matching deletion/contraction, etc. We present two algorithms. The first one solves ℒ-Replacement to ℋ in time 2^poly(k) ⋅ |V(G)|² for every minor-closed graph class ℋ, where poly is a polynomial whose degree depends on ℋ, under a mild technical condition on ℒ. This generalizes the results of Morelle, Sau, Stamoulis, and Thilikos [ICALP 2020, ICALP 2023] for the particular case of Vertex Deletion to ℋ within the same running time. Our second algorithm is an improvement of the first one when ℋ is the class of graphs embeddable in a surface of Euler genus at most g and runs in time 2^𝒪(k⁹) ⋅ |V(G)|², where the 𝒪(⋅) notation depends on g. To the best of our knowledge, these are the first parameterized algorithms with a reasonable parametric dependence for such a general family of graph modification problems to minor-closed classes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Laure Morelle and Ignasi Sau and Dimitrios M. Thilikos 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.7 urn:nbn:de:0030-drops-244751 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.7 eng https://creativecommons.org/licenses/by/4.0/legalcode