2020/04/27 by Ignasi Sau, Sau, Ignasi, Giannos Stamoulis +3 · 3 citations
Computer Science · Mathematics · #05C69 #05C75 #05C83 #05C85 #68R10 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Algorithm #Apex (geometry) #Combinatorics #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete mathematics #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Geometry #Graph #Graph Labeling and Dimension Problems #Humanities #Limits and Structures in Graph Theory #Mathematics #Minor (academic) #Parameterized complexity #acm:05C69 #acm:05C75 #acm:05C83 #acm:05C85 #acm:68R10 #cs.CC #cs.DS #math.CO #msc:05C69 #msc:05C75 #msc:05C83 #msc:05C85 #msc:68R10
paper · pdf · open access · doi:10.48550/arxiv.2004.12692
published in arXiv (Cornell University) (Cornell University) · 37 pages, 3 figures
openalex publication_date 2020/04/27 · arxiv created 2021/03/02 · arxiv updated 2021/03/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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.