TY - GEN

T1 - Computing cut-based hierarchical decompositions in almost linear time

AU - Räcke, Harald

AU - Shah, Chintan

AU - Täubig, Hanjo

PY - 2014

Y1 - 2014

N2 - We present a fast construction algorithm for the hierarchical tree decompositions that lie at the heart of oblivious routing strategies and that form the basis for approximation and online algorithms for various cut problems in graphs. Given an undirected graph G = (V, E, c) with edge capacities, we compute a single tree T = (Vt,Et,Ct), where the leaf nodes of T correspond to nodes in G. such that the tree approximates the cut-structure of G up to a factor of O(log4 n). The best existing construction by Harrelson, Hildrum, and Rao [12] just guarantees a polynomial running time but offers a better approximation guarantee of O(log2 n log log n). Phrasing our results in terms of vertex sparsifiers, we obtain the following: For a graph G = (V, E) with a subset S of terminals, we compute a tree T with at most 2IS| vertices (and the leafs of T correspond to nodes in S) such that T is a flow-sparsifier for S in G with quality O(log2 nlog2 k), where |V| = n and |S| = k. The running time is O(polylog n . T(m, 1/log3 n)) where T(m, e) is the time for computing an approximate maxflow in a graph with m edges. The latter is almost linear due to the recent results of Sherman [23] and Kelner et al. [13].

AB - We present a fast construction algorithm for the hierarchical tree decompositions that lie at the heart of oblivious routing strategies and that form the basis for approximation and online algorithms for various cut problems in graphs. Given an undirected graph G = (V, E, c) with edge capacities, we compute a single tree T = (Vt,Et,Ct), where the leaf nodes of T correspond to nodes in G. such that the tree approximates the cut-structure of G up to a factor of O(log4 n). The best existing construction by Harrelson, Hildrum, and Rao [12] just guarantees a polynomial running time but offers a better approximation guarantee of O(log2 n log log n). Phrasing our results in terms of vertex sparsifiers, we obtain the following: For a graph G = (V, E) with a subset S of terminals, we compute a tree T with at most 2IS| vertices (and the leafs of T correspond to nodes in S) such that T is a flow-sparsifier for S in G with quality O(log2 nlog2 k), where |V| = n and |S| = k. The running time is O(polylog n . T(m, 1/log3 n)) where T(m, e) is the time for computing an approximate maxflow in a graph with m edges. The latter is almost linear due to the recent results of Sherman [23] and Kelner et al. [13].

UR - http://www.scopus.com/inward/record.url?scp=84902096376&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973402.17

DO - 10.1137/1.9781611973402.17

M3 - Conference contribution

AN - SCOPUS:84902096376

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 227

EP - 238

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery

T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

Y2 - 5 January 2014 through 7 January 2014

ER -