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)root 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(root hnm) time such a separator or a K(h)-minor of G. Plotkin, Rao, and Smith gave an O(hm root n log n) time algorithm to find a separator of size O(h root n log n). Kawarabayashi and Reed improved the bound on the size of the separator to h root n and gave an algorithm that finds such a separator in O(n(1+c)) time for any constant is an element of > 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 root n log n)-size separator or report that G has a K(h)-minor in O(poly(h)n(5/4+is an element of)) time for any constant is an element of > 0. We also present the first O(poly(h)n) time algorithm to find a separator of size O(n(c)) for a constant c <1. As corollaries of our results, we get improved algorithms for shortest paths and maximum matching. Furthermore, for integers l and h, we give an O(m + n(2+is an element of)/l) time algorithm that either produces a K(h)-minor of depth O(l log n) or a separator of size at most O(n/l + lh(2) log n). This improves the shallow minor algorithm of Plotkin, Rao, and Smith when m = Omega(n(1+is an element of)). We get a similar running time improvement for an approximation algorithm for the problem of finding a largest.. h-minor in a given graph.