Chandran, L. Sunil ;
Cheung, Yun Kuen ;
Issac, Davis
Spanning Tree Congestion and Computation of Generalized GyöriLovász Partition
Abstract
We study a natural problem in graph sparsification, the Spanning Tree Congestion (STC) problem. Informally, it seeks a spanning tree with no treeedge routing too many of the original edges.
For any general connected graph with n vertices and m edges, we show that its STC is at most O(sqrt{mn}), which is asymptotically optimal since we also demonstrate graphs with STC at least Omega(sqrt{mn}). We present a polynomialtime algorithm which computes a spanning tree with congestion O(sqrt{mn}* log n). We also present another algorithm for computing a spanning tree with congestion O(sqrt{mn}); this algorithm runs in subexponential time when m = omega(n log^2 n).
For achieving the above results, an important intermediate theorem is generalized GyöriLovász theorem. Chen et al. [Jiangzhuo Chen et al., 2007] gave a nonconstructive proof. We give the first elementary and constructive proof with a local search algorithm of running time O^*(4^n). We discuss some consequences of the theorem concerning graph partitioning, which might be of independent interest.
We also show that for any graph which satisfies certain expanding properties, its STC is at most O(n), and a corresponding spanning tree can be computed in polynomial time. We then use this to show that a random graph has STC Theta(n) with high probability.
BibTeX  Entry
@InProceedings{chandran_et_al:LIPIcs:2018:9036,
author = {L. Sunil Chandran and Yun Kuen Cheung and Davis Issac},
title = {{Spanning Tree Congestion and Computation of Generalized Gy{\"o}riLov{\'a}sz Partition}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {32:132:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9036},
URN = {urn:nbn:de:0030drops90361},
doi = {10.4230/LIPIcs.ICALP.2018.32},
annote = {Keywords: Spanning Tree Congestion, Graph Sparsification, Graph Partitioning, MinMax Graph Partitioning, kVertexConnected Graphs, Gy{\"o}riLov{\'a}sz Theorem}
}
2018
Keywords: 

Spanning Tree Congestion, Graph Sparsification, Graph Partitioning, MinMax Graph Partitioning, kVertexConnected Graphs, GyöriLovász Theorem 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

2018 