## 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^{22poly}(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^{2O}(^{k2 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}.

Original language | English (US) |
---|---|

Title of host publication | 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 |

Editors | Kousha Etessami, Uriel Feige, Gabriele Puppis |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959772785 |

DOIs | |

State | Published - Jul 2023 |

Event | 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 - Paderborn, Germany Duration: Jul 10 2023 → Jul 14 2023 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 261 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 |
---|---|

Country/Territory | Germany |

City | Paderborn |

Period | 7/10/23 → 7/14/23 |

## Keywords

- Elimination distance
- Flat Wall Theorem
- Graph minors
- Graph modification problems
- Irrelevant vertex technique
- Obstructions
- Parameterized algorithms
- Vertex deletion

## ASJC Scopus subject areas

- Software