TY - GEN
T1 - An FPT-algorithm for recognizing k-apices of minor-closed graph classes
AU - Sau, Ignasi
AU - Stamoulis, Giannos
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).
PY - 2020/6/1
Y1 - 2020/6/1
N2 - 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 2poly(k)n3 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 2poly(k)n2 time.
AB - 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 2poly(k)n3 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 2poly(k)n2 time.
KW - Graph minors
KW - Graph modification problems
KW - Irrelevant vertex technique
KW - Parameterized algorithms
UR - http://www.scopus.com/inward/record.url?scp=85089340915&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089340915&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2020.95
DO - 10.4230/LIPIcs.ICALP.2020.95
M3 - Conference contribution
AN - SCOPUS:85089340915
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
A2 - Czumaj, Artur
A2 - Dawar, Anuj
A2 - Merelli, Emanuela
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
Y2 - 8 July 2020 through 11 July 2020
ER -