2026-07-22T06:21:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12502 2024-03-06T10:50:18Z ddc:004 open_access

An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes Sau, Ignasi Stamoulis, Giannos Thilikos, Dimitrios M. Graph modification problems irrelevant vertex technique graph minors parameterized algorithms Let G be a graph class. We say that a graph 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. We prove that if G is minor-closed, then there is an algorithm that either returns a set S certifying that G is a k-apex of G or reports that such a set does not exist, in 2^{poly(k)}n³ time. Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G, i.e., the minor-minimal set of graphs not belonging to G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2^{poly(k)}n² time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ignasi Sau and Giannos Stamoulis and Dimitrios M. Thilikos 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.95 urn:nbn:de:0030-drops-125027 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.95 eng https://creativecommons.org/licenses/by/3.0/legalcode