TY - JOUR

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

AU - Sau, Ignasi

AU - Stamoulis, Giannos

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© 2022 Association for Computing Machinery.

PY - 2022/10/11

Y1 - 2022/10/11

N2 - 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.

AB - 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.

KW - flat wall theorem

KW - Graph minors

KW - graph modification problems

KW - irrelevant vertex technique

KW - parameterized algorithms

UR - http://www.scopus.com/inward/record.url?scp=85134716234&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85134716234&partnerID=8YFLogxK

U2 - 10.1145/3519028

DO - 10.1145/3519028

M3 - Article

AN - SCOPUS:85134716234

SN - 1549-6325

VL - 18

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 3

M1 - 21

ER -