Abstract
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.
| Originalsprog | Engelsk |
|---|---|
| Titel | Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on |
| Antal sider | 10 |
| Forlag | IEEE Computer Society Press |
| Publikationsdato | 2011 |
| Sider | 37-46 |
| ISBN (Trykt) | 978-1-4577-1843-4 |
| DOI | |
| Status | Udgivet - 2011 |
| Udgivet eksternt | Ja |
| Begivenhed | 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science - Palm Springs, California, USA Varighed: 22 okt. 2011 → 25 okt. 2011 Konferencens nummer: 52 |
Konference
| Konference | 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science |
|---|---|
| Nummer | 52 |
| Land/Område | USA |
| By | Palm Springs, California |
| Periode | 22/10/2011 → 25/10/2011 |
Emneord
- computational complexity
- graph theory
- polynomials
- Ku-minor
- approximation algorithm
- polynomial time dependency
- separator theorems
- shallow minor free graphs
- time algorithm
- Algorithm design and analysis
- Approximation algorithms
- Approximation methods
- Clustering algorithms
- Heuristic algorithms
- Particle separators
- Partitioning algorithms
- maximum matching
- minor-free graph
- separator
- shallow minor-free graph
- shortest path