Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with\n Applications

2011/07/07 by Christian Wulff-Nilsen, Christian Wulff‐Nilsen, Wulff-Nilsen, Christian · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #Discrete mathematics #FOS: Computer and information sciences #G.2.2 #Graph #Mathematical analysis #Mathematics #Minor (academic) #Optimization and Search Problems #Physics #Planar graph #Separator (oil production) #Thermodynamics #Upper and lower bounds #cs.DM

paper · pdf · doi:10.48550/arxiv.1107.1292

published in arXiv (Cornell University) (Cornell University) · To appear at FOCS 2011

arxiv created 2011/07/07 · openalex publication_date 2011/07/07 · arxiv updated 2011/07/08 · openalex created_date 2022/10/03 · openalex updated_date 2026/08/05

Abstract

Alon, Seymour, and Thomas generalized Lipton and Tarjan's planar separator\ntheorem and showed that a K_h-minor free graph with n vertices has a\nseparator of size at most h^3/2\√ n. They gave an algorithm that, given\na graph G with m edges and n vertices and given an integer h\≥ 1,\noutputs in O(\√(hn)m) time such a separator or a K_h-minor of G.\nPlotkin, Rao, and Smith gave an O(hm\√(n\log n)) time algorithm to find a\nseparator of size O(h\√(n\log n)). Kawarabayashi and Reed improved the\nbound on the size of the separator to h\√ n and gave an algorithm that\nfinds such a separator in O(n^{1 + \ε}) time for any constant \ε\n> 0, assuming h is constant. This algorithm has an extremely large\ndependency on h in the running time (some power tower of h whose height is\nitself a function of h), making it impractical even for small h. We are\ninterested in a small polynomial time dependency on h and we show how to find\nan O(h\√(n\log n))-size separator or report that G has a K_h-minor in\nO( poly(h)n^{5/4 + \ε}) time for any constant \ε > 0. We also\npresent the first O( poly(h)n) time algorithm to find a separator of size\nO(n^c) for a constant c < 1. As corollaries of our results, we get improved\nalgorithms for shortest paths and maximum matching. Furthermore, for integers\n\ℓ and h, we give an O(m + n^{2 + \ε}/\ℓ) time algorithm that\neither produces a K_h-minor of depth O(\ℓ\log n) or a separator of size\nat most O(n/\ℓ + \ℓ h²\log n). This improves the shallow minor algorithm\nof Plotkin, Rao, and Smith when m = \Ω(n^{1 + \ε}). We get a\nsimilar running time improvement for an approximation algorithm for the problem\nof finding a largest K_h-minor in a given graph.\n

Citations

• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Applications of a Planar Separator Theorem
• Approximating the maximum clique minor and some subgraph homeomorphism problems

Cited by

• Separator Theorem for Minor-Free Graphs in Linear Time
• Faster shortest-path algorithms using the acyclic-connected tree

Related

• Separator Theorem for Minor-Free Graphs in Linear Time
• Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition
• A linear-time algorithm to find a separator in a graph excluding a minor
• Minor Containment and Disjoint Paths in almost-linear time
• Finding forbidden minors in sublinear time: a n^1/2+o(1)-query one-sided tester for minor closed properties on bounded degree graphs