文章基本信息

标题：An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes
本地全文：下载
作者：Ignasi Sau ; Giannos Stamoulis ; Dimitrios M. Thilikos 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：95:1-95:20
DOI：10.4230/LIPIcs.ICALP.2020.95
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Graph modification problems; irrelevant vertex technique; graph minors; parameterized algorithms