2020/04/27 by Sau, Ignasi, Stamoulis, Giannos, Thilikos, Dimitrios M. · 1 citation
#05C69 #05C75 #05C83 #05C85 #68R10 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2004.12692
Let \cal G be a minor-closed graph class. We say that a graph G is a k-apex of \cal G if G contains a set S of at most k vertices such that G∖ S belongs to \cal G. We denote by \cal Ak (\cal G) the set of all graphs that are k-apices of \cal G. In the first paper of this series we obtained upper bounds on the size of the graphs in the minor-obstruction set of \cal Ak (\cal G), i.e., the minor-minimal set of graphs not belonging to \cal Ak (\cal G). In this article we provide an algorithm that, given a graph G on n vertices, runs in 2^\sf poly(k)⋅ n3-time and either returns a set S certifying that G ∈ \cal Ak (\cal G), or reports that G ∉ \cal Ak (\cal G). Here \sf poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of \cal G. In the special case where \cal G excludes some apex graph as a minor, we give an alternative algorithm running in 2^\sf poly(k)⋅ n2-time.