Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Spanning Tree Congestion and the Generalized Győri-Lovász Theorem (Part 1)
Speaker:L. Sunil Chandran and Davis Issac
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 9 November 2017
Duration:30 Minutes
Building:E1 4

We study a natural problem in graph sparsification, the Spanning Tree Congestion (STC) problem. Informally, the STC problem seeks a spanning tree such that no tree-edge routes too many of the original edges. The root of this problem dates back to at least 30 years ago, with motivations from applications in network design, parallel computing and circuit design. Variants of the problem have also seen great algorithmic applications as a preprocessing step of several important graph algorithms.

We focus on three scenarios: (a) general connected graphs with $n$ vertices and $m$ edges, (b) random graphs and (c) graphs with very high minimum degree. For all these scenarios, we prove tight bounds on the spanning tree congestion (STC). For (a), we show that the STC is at most $\O(\sqrt{mn})$. We present an algorithm for computing such a spanning tree, which runs in sub-exponential time when $m = \omega(n \log^2 n)$. We also demonstrate graphs with STC at least $\Omega(\sqrt{mn})$. For (b) and (c), we prove that the STC are $\Theta(n)$ (with high probability) and $\Theta(n)$ respectively, and we present constant-approximation polynomial time algorithms that compute such a spanning tree.

For establishing these results, an important intermediate theorem is a generalization of the Győri-Lovász theorem. The classical Győri-Lovász theorem was proved in the 1970's, which states: for any $k$-vertex-connected graph $G=(V,E)$, $k$ distinct terminal vertices $t_1,\cdots,t_k$, and $k$ positive integers $n_1,\cdots,n_k$ which sum to $|V|$, there always exists a partition of $V$ into $k$ sets, such that (i) the $j$-th set contains the terminal $t_j$; (ii) the cardinality of the $j$-th set is exactly $n_j$; and crucially, (iii) each set induces a \emph{connected} subgraph. In this paper, we prove a natural generalization of this theorem, in which the vertices have positive real weights, and the partitioning requirement is on the sum of vertex weights in each set. We present an $\Os\left( 4^n \right)$ algorithm for finding such a partition; if we need only $k/2$ sets instead of $k$, the algorithm's running time improves to $\Os(2^{\O((n/k)\log k)})$.

The generalized Győri-Lovász theorem implies the following result concerning graph partitioning: for any $k$-vertex-connected graph with $m$ edges, there exists a $k$-partition that satisfies (i) and (iii), and the number of edges leaving each set is at most $4m/k$, which is optimal up to a constant factor.

Name(s):Yun Kuen Cheung
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Yun Kuen Cheung, 11/03/2017 08:53 PM
Last modified:
Uwe Brahm/MPII/DE, 11/09/2017 07:00 AM
  • Yun Kuen Cheung, 11/08/2017 06:13 PM
  • Yun Kuen Cheung, 11/03/2017 08:54 PM
  • Yun Kuen Cheung, 11/03/2017 08:53 PM -- Created document.