A replacement action is a function $\mathcal{L}$ that maps each graph $H$ to
a collection of graphs of size at most $|V(H)|$. 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 present two algorithms. The first one solves
$\mathcal{L}$-Replacement to $\mathcal{H}$ in time $2^{{\rm poly}(k)}\cdot
|V(G)|^2$ for every minor-closed graph class $\mathcal{H}$, where {\rm poly} is
a polynomial whose degree depends on $\mathcal{H}$, under a mild technical
condition on $\mathcal{L}$. This generalizes the results of Morelle, Sau,
Stamoulis, and Thilikos [ICALP 2020, ICALP 2023] for the particular case of
Vertex Deletion to $\mathcal{H}$ within the same running time. Our second
algorithm is an improvement of the first one when $\mathcal{H}$ is the class of
graphs embeddable in a surface of Euler genus at most $g$ and runs in time
$2^{\mathcal{Ô}(k^{9})}\cdot |V(G)|^2$, where the $\mathcal{Ô}(\cdot)$ 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.

Cet article explore les excursions dans le temps et leurs implications.

Télécharger PDF: