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

Alon, Seymour, and Thomas generalized Lipton and Tarjan´s planar separator theorem and showed that a K_h- minor free graph with n vertices has a separator of size at most h^3/2 √n. They gave an algorithm that, given a graph G with m edges and n vertices and given an integer h ≥ 1, outputs in O(√hnm) time such a separator or a Ku-minor of G. Plotkin, Rao, and Smith gave an O(hm√/n log n) time algorithm to find a separator of size O(h√n log n). Kawarabayashi and Reed improved the bound on the size of the separator to h√n and gave an algorithm that finds such a separator in O(n^1+ϵ) time for any constant ϵ >; 0, assuming h is constant. This algorithm has an extremely large dependency on h in the running time (some power tower of h whose height is itself a function of h), making it impractical even for small h. We are interested in a small polynomial time dependency on h and we show how to find an O (h√n log n)-size separator or report that G has a Ku-minor in O(poly(h)n^5/4+ϵ) time for any constant ϵ >; 0. We also present the first O(poly(h)n) time algorithm to find a separator of size 0(n^c) for a constant ϵ <; 1. As corollaries of our results, we get improved algorithms for shortest paths and maximum matching. Furthermore, for integers ℓ and h, we give an O(m ,^{2 + ϵ} /ℓ) time algorithm that either produces a K_h-minor of depth O(ℓ log n) or a separator of size at most O(n/ℓ + ℓh²log n). This improves the shallow minor algorithm of Plotkin, Rao, and Smith when m = Ω(n1+ϵ). We get a similar running time improvement for an approximation algorithm for the problem of finding a largest K_h -minor in a given graph.