Faster parameterized algorithms for modification problems to minor-closed classes - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2023

Faster parameterized algorithms for modification problems to minor-closed classes

Laure Morelle
Ignasi Sau
Giannos Stamoulis

Abstract

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. This algorithm improves the previous one, given by Sau, Stamoulis, and Thilikos [ICALP 2020, TALG 2022], whose running time was 2 poly(k) • n^3. The elimination distance of G to G, denoted by edG(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] proved the existence of an FPT-algorithm, with parameter k, to decide whether edG(G) ≤ k. This algorithm is based on the computability of the minor-obstructions and its dependence on k is not explicit. We extend the techniques used in the first algorithm to decide whether edG(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, one running in time 2^2^O(k 2 log k) • n 2 and one running in time 2 poly(k) • n^3. As a stepping stone for these algorithms, we provide an algorithm that decides whether edG(G) ≤ k in time 2 O(tw•k+tw log tw) • n, where tw is the treewidth of G. This algorithm combines the dynamic programming framework of Reidl, Rossmanith, Villaamil, and Sikdar [ICALP 2014] for the particular case where G contains only the empty graph (i.e., for treedepth) with the representative-based techniques introduced by Baste, Sau, and Thilikos [SODA 2020]. In all the algorithmic complexities above, poly is a polynomial function whose degree depends on G, while the hidden constants also depend on 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 | edG(G) ≤ k}.
Fichier principal
Vignette du fichier
Efficient2.0.pdf (848.23 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-04253814 , version 1 (23-10-2023)

Identifiers

Cite

Laure Morelle, Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos. Faster parameterized algorithms for modification problems to minor-closed classes. ICALP 2023 - 50th International Colloquium on Automata, Languages and Programming, Jul 2023, Paderborn, Germany. pp.93:1-93:19, ⟨10.4230/LIPIcs.ICALP.2023.93⟩. ⟨lirmm-04253814⟩
8 View
8 Download

Altmetric

Share

Gmail Facebook X LinkedIn More