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$.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.