Faster parameterized algorithms for modification problems to minor-closed classes

MaRDI QIDQ6412955zbMATH OpenFDO

Authors Laure Morelle, Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos

Publication date 5 October 2022

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Abstract: Let $calG$ be a minor-closed graph class and let $G$ be an $n$-vertex graph. We say that $G$ is a $k$-apex of $calG$ if $G$ contains a set $S$ of at most $k$ vertices such that $GsetminusS$ belongs to $calG$. Our first result is an algorithm that decides whether $G$ is a $k$-apex of $calG$ in time $2^{sfpoly(k)}cdot{n}^2$, where $sfpoly$ is a polynomial function depending on $calG$. This algorithm improves the previous one, given by Sau, Stamoulis, and Thilikos [ICALP 2020], whose running time was $2^{sfpoly(k)}cdot{n}^3$. The elimination distance of $G$ to $calG$, denoted by ${sfed}_{calG}(G)$, is the minimum number of rounds required to reduce each connected component of $G$ to a graph in $calG$ by removing one vertex from each connected component in each round. Bulian and Dawar [Algorithmica 2017] provided an FPT-algorithm, with parameter $k$, to decide whether ${sfed}_{calG}(G)leqk$. However, its dependence on $k$ is not explicit. We extend the techniques used in the first algorithm to decide whether ${sfed}_{calG}(G)leqk$ in time $2^{2^{2^{sfpoly(k)}}}cdot{n}^2$. This is the first algorithm for this problem with an explicit parametric dependence in $k$. In the special case where $calG$ excludes some apex-graph as a minor, we give two alternative algorithms, running in time $2^{2^{calO(k^{2}logk)}}cdot{n}^2$ and $2^{sfpoly(k)}cdot{n}^3$ respectively, where $c$ and $sfpoly$ depend on $calG$. As a stepping stone for these algorithms, we provide an algorithm that decides whether ${sfed}_{calG}(G)leqk$ in time $2^{calO(sftwcdotk+sftwlogsftw)}cdotn$, where $sftw$ is the treewidth of $G$. Finally, we provide explicit upper bounds on the size of the graphs in the minor-obstruction set of the class of graphs ${calE}_k(calG)=Gmid{sfed}_{calG}(G)leqk$.

This page was built for publication: Faster parameterized algorithms for modification problems to minor-closed classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6412955)