Résumé
A replacement action is a function L that maps each graph H to a collection of graphs of size at most |V (H)|. Given a graph class H, we consider a general family of graph modification problems, called L-Replacement to H, where the input is a graph G and the question is whether it is possible to replace some induced subgraph H1 of G on at most k vertices by a graph H2 in L(H1) so that the resulting graph belongs to H. L-Replacement to H 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 L-Replacement to H in time 2 poly(k) • |V (G)| 2 for every minor-closed graph class H, where poly is a polynomial whose degree depends on H, under a mild technical condition on L. This generalizes the results of Morelle, Sau, Stamoulis, and Thilikos [ICALP 2020, ICALP 2023] for the particular case of Vertex Deletion to H within the same running time. Our second algorithm is an improvement of the first one when H is the class of graphs embeddable in a surface of Euler genus at most g and runs in time 2 O(k 9 ) • |V (G)| 2 , where the O(•) 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.