Laure Morelle, Bounded size modifications in time $2^{\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}(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^{\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}(k)}\cdot |V(G){|}^2$, where $\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}$ is a polynomial whose degree depends on $\mathcal{H}$.