Laure Morelle, Bounded size modifications in time $2^{{\sf poly}(k)}\cdot n^2$

A replacement action is a function $\mathcal L$ that maps each graph to a collection of subgraphs of smaller size.

Given a graph class $\mathcal H$, we consider a general family of graph modification problems, called “$\mathcal L$-Replacement to $\mathcal H$”, where the input is a graph $G$ and the question is whether it is possible to replace some induced subgraph $H_1$ of $G$ on at most $k$ vertices by a graph $H_2$ in ${\mathcal L}(H_1)$ so that the resulting graph belongs to $\mathcal H$.

“$\mathcal L$-Replacement to $\mathcal 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 prove here that, for any minor-closed graph class $\mathcal H$ and for any action $\mathcal L$ that is hereditary, there is an algorithm that solves “$\mathcal L$-Replacement to $\mathcal H$” in time $2^{{\sf poly}(k)}\cdot |V(G)|^2$, where $\sf poly$ is a polynomial whose degree depends on $\mathcal H$.