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

TY - GEN

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

AU - Wulff-Nilsen, C.

N1 - Conference code: 52

PY - 2011

Y1 - 2011

N2 - 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 K h-minor of G. Plot kin, Rao, and Smith gave an O(hm√n log n) time algorithm to find a separator of size O(h√n log n). Kawara bayashi 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 K h-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 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 ℓ and h, we give an O(m + n 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 2 log n). This improves the shallow minor algorithm of Plotkin, Rao, and Smith when m = Ω(n 1+ε). 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.

AB - 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 K h-minor of G. Plot kin, Rao, and Smith gave an O(hm√n log n) time algorithm to find a separator of size O(h√n log n). Kawara bayashi 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 K h-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 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 ℓ and h, we give an O(m + n 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 2 log n). This improves the shallow minor algorithm of Plotkin, Rao, and Smith when m = Ω(n 1+ε). 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.

KW - computational complexity

KW - graph theory

KW - polynomials

KW - Ku-minor

KW - approximation algorithm

KW - polynomial time dependency

KW - separator theorems

KW - shallow minor free graphs

KW - time algorithm

KW - Algorithm design and analysis

KW - Approximation algorithms

KW - Approximation methods

KW - Clustering algorithms

KW - Heuristic algorithms

KW - Particle separators

KW - Partitioning algorithms

KW - maximum matching

KW - minor-free graph

KW - separator

KW - shallow minor-free graph

KW - shortest path

U2 - 10.1109/FOCS.2011.15

DO - 10.1109/FOCS.2011.15

M3 - Article in proceedings

SN - 978-1-4577-1843-4

SP - 37

EP - 46

BT - Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on

PB - IEEE Computer Society Press

T2 - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science

Y2 - 22 October 2011 through 25 October 2011

ER -