κ-Apices of Minor-closed Graph Classes. II. Parameterized Algorithms

Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

Let be a minor-closed graph class. We say that a graph G is a k-Apex of if G contains a set S of at most k vertices such that G\S belongs to . We denote by k () the set of all graphs that are k-Apices of . In the first paper of this series, we obtained upper bounds on the size of the graphs in the minor-obstruction set of k (), i.e., the minor-minimal set of graphs not belonging to k (). In this article, we provide an algorithm that, given a graph G on n vertices, runs in time 2poly(k) (k). n3 and either returns a set S certifying that G €k (G), or reports that G g‰ Ak (G). Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of . In the special case where excludes some apex graph as a minor, we give an alternative algorithm running in 2poly(k)n2-Time.

Original languageEnglish (US)
Article number21
JournalACM Transactions on Algorithms
Volume18
Issue number3
DOIs
StatePublished - Oct 11 2022

Keywords

  • flat wall theorem
  • Graph minors
  • graph modification problems
  • irrelevant vertex technique
  • parameterized algorithms

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'κ-Apices of Minor-closed Graph Classes. II. Parameterized Algorithms'. Together they form a unique fingerprint.

Cite this