Faster parameterized algorithms for modification problems to minor-closed classes
share
Let G be a minor-closed graph class and let G be an n-vertex graph. We say that G is a k-apex of G if G contains a set S of at most k vertices such that G∖ S belongs to G. Our first result is an algorithm that decides whether G is a k-apex of G in time 2^ poly(k)· n^2, where poly is a polynomial function depending on G. This algorithm improves the previous one, given by Sau, Stamoulis, and Thilikos [ICALP 2020], whose running time was 2^ poly(k)· n^3. The elimination distance of G to G, denoted by ed_ G(G), is the minimum number of rounds required to reduce each connected component of G to a graph in G 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 ed_ G(G)≤ k. However, its dependence on k is not explicit. We extend the techniques used in the first algorithm to decide whether ed_ G(G)≤ k in time 2^2^2^ poly(k)· n^2. This is the first algorithm for this problem with an explicit parametric dependence in k. In the special case where G excludes some apex-graph as a minor, we give two alternative algorithms, running in time 2^2^ O(k^2log k)· n^2 and 2^ poly(k)· n^3 respectively, where c and poly depend on G. As a stepping stone for these algorithms, we provide an algorithm that decides whether ed_ G(G)≤ k in time 2^ O( tw· k+ twlog tw)· n, where tw 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 E_k( G)={G| ed_ G(G)≤ k}.
READ FULL TEXT