Faster separators for shallow minor-free graphs via dynamic approximate distance oracles

TY - GEN

T1 - Faster separators for shallow minor-free graphs via dynamic approximate distance oracles

AU - Wulff-Nilsen, Christian

N1 - Conference code: 41

PY - 2014

Y1 - 2014

N2 - Plotkin, Rao, and Smith (SODA'97) showed that any graph with m edges and n vertices that excludes Kh as a depth O(ℓlogn)-minor has a separator of size O(n/ℓ+ℓh2logn) and that such a separator can be found in O(mn/ℓ) time. A time bound of O(m+n2+ε /ℓ) for any constant ε>0 was later given (W., FOCS'11) which is an improvement for non-sparse graphs. We give three new algorithms. The first two have the same separator size (the second having a slightly larger dependency on h) and running time O(poly(h)ℓn1+ε) and O(poly(h) (√ℓn1+ε + n2+ε/ℓ3/2)), respectively. The former is significantly faster than previous bounds for small h and ℓ. Our third algorithm has running time O(poly(h)(√ℓn 1+ε). It finds a separator of size O(n/ℓ) + Õ(poly(h)(ℓ√n) which is no worse than previous bounds when h is fixed and ℓ = Õ(n1/4. A main tool in obtaining our results is a decremental approximate distance oracle of Roditty and Zwick.

AB - Plotkin, Rao, and Smith (SODA'97) showed that any graph with m edges and n vertices that excludes Kh as a depth O(ℓlogn)-minor has a separator of size O(n/ℓ+ℓh2logn) and that such a separator can be found in O(mn/ℓ) time. A time bound of O(m+n2+ε /ℓ) for any constant ε>0 was later given (W., FOCS'11) which is an improvement for non-sparse graphs. We give three new algorithms. The first two have the same separator size (the second having a slightly larger dependency on h) and running time O(poly(h)ℓn1+ε) and O(poly(h) (√ℓn1+ε + n2+ε/ℓ3/2)), respectively. The former is significantly faster than previous bounds for small h and ℓ. Our third algorithm has running time O(poly(h)(√ℓn 1+ε). It finds a separator of size O(n/ℓ) + Õ(poly(h)(ℓ√n) which is no worse than previous bounds when h is fixed and ℓ = Õ(n1/4. A main tool in obtaining our results is a decremental approximate distance oracle of Roditty and Zwick.

U2 - 10.1007/978-3-662-43948-7_88

DO - 10.1007/978-3-662-43948-7_88

M3 - Article in proceedings

SN - 978-3-662-43947-0

T3 - Lecture notes in computer science

SP - 1063

EP - 1074

BT - Automata, languages, and programming

A2 - Esparza, Javier

A2 - Fraigniaud, Pierre

A2 - Husfeldt, Thore

A2 - Koutsoupias, Elias

PB - Springer

T2 - 41st International Colloquium on Automata, Languages, and Programming

Y2 - 8 July 2014 through 11 July 2014

ER -