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 Computation of Generalized Gyori-Lovasz Partition
Speaker:Davis Issac
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 28 June 2018
Duration:30 Minutes
Building:E1 4
We study a natural problem in graph sparsification, the Spanning Tree Congestion (STC) problem. Informally, it seeks a spanning tree with no tree-edge \emph{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 polynomial-time algorithm which computes a spanning tree with congestion $O(\sqrt{mn}\cdot \log n)$.We also present another algorithm for computing a spanning tree with congestion $O(\sqrt{mn})$; this algorithm runs in sub-exponential time when $m = \omega(n \log^2 n)$.

For achieving the above results, an important intermediate theorem is generalized Gy\H{o}ri-Lov{\'{a}}sz theorem. Chen et al. in 2007 gave a non-constructive proof. We give the first elementary and constructive proof with a local search algorithm of running time $O^*\left( 4^n \right)$. 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.

Name(s):Davis Issac
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Davis Issac, 05/03/2018 05:37 PM
Last modified:
halma/MPII/DE, 04/16/2019 12:00 AM
  • Davis Issac, 05/03/2018 05:37 PM -- Created document.