Spanning tree congestion and computation of generalized Győri-Lovász partition

DOI10.4230/LIPICS.ICALP.2018.32MaRDI QIDQ5002702zbMATH OpenOpenAlexFDO

Authors L. Sunil Chandran, Yun Kuen Cheung, Davis Issac

Publication date 28 July 2021

Full work available at URL https://arxiv.org/abs/1802.07632

zbMATH Keywords

\(k\)-vertex-connected graphsgraph partitioninggraph sparsificationGyőri-Lovász theoremMIN-MAX graph partitioningspanning tree congestion

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: We study a natural problem in graph sparsification, the Spanning Tree Congestion (STC) problem. Informally, the STC problem seeks a spanning tree with no tree-edge emph{routing} too many of the original edges. The root of this problem dates back to at least 30 years ago, motivated by applications in network design, parallel computing and circuit design. Variants of the problem have also seen algorithmic applications as a preprocessing step of several important graph algorithms. For any general connected graph with $n$ vertices and $m$ edges, we show that its STC is at most $mathcalO(sqrtmn)$, which is asymptotically optimal since we also demonstrate graphs with STC at least $Omega(sqrtmn)$. We present a polynomial-time algorithm which computes a spanning tree with congestion $mathcalO(sqrtmncdotlogn)$. We also present another algorithm for computing a spanning tree with congestion $mathcalO(sqrtmn)$; this algorithm runs in sub-exponential time when $m=omega(nlo{g}^{2}n)$. For achieving the above results, an important intermediate theorem is emph{generalized GyH{o}ri-Lov'{a}sz theorem}, for which Chen et al. gave a non-constructive proof. We give the first elementary and constructive proof by providing a local search algorithm with running time $mathcal{O}^{\ast }left(4^{n}ight)$, which is a key ingredient of the above-mentioned sub-exponential time algorithm. We discuss a few consequences of the theorem concerning graph partitioning, which might be of independent interest. We also show that for any graph which satisfies certain emph{expanding properties}, its STC is at most $mathcalO(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.

Recommendations

• On spanning tree congestion
• Minimum congestion spanning trees in bipartite and random graphs
• On spanning tree congestion of graphs
• Complexity results for the spanning tree congestion problem
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem

Cites work

• (Almost) Tight bounds and existence theorems for single-commodity confluent flows
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A homology theory for spanning tress of a graph
• A linear algorithm for bipartition of biconnected graphs
• A Nearly-m log n Time Solver for SDD Linear Systems
• A variation on the min cut linear arrangement problem
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem
• How easy is local search?
• scientific article; zbMATH DE number 3603293 (Why is no real title available?)
• Lower-Stretch Spanning Trees
• Min-Max Graph Partitioning and Small Set Expansion
• Min-max-boundary domain decomposition
• Minimal congestion trees
• Minimum congestion spanning trees in bipartite and random graphs
• Minimum congestion spanning trees in planar graphs
• On spanning tree congestion
• On spanning tree congestion of graphs
• Parameterized complexity of the spanning tree congestion problem
• Spanning tree congestion of k-outerplanar graphs
• Spanning tree congestion of planar graphs
• Spanning tree congestion of rook's graphs
• Using petal-decompositions to build a low stretch spanning tree

Cited in

(11)

• A diameter-revealing proof of the Bondy-Lovász lemma
• A Survey on Spanning Tree Congestion
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem
• Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs
• Better hardness results for the minimum spanning tree congestion problem
• Approximation of spanning tree congestion using hereditary bisection
• Parameterized spanning tree congestion
• Connected partitions via connected dominating sets
• Approximation algorithms for connected k-edge partition
• Approximation of spanning tree congestion using hereditary bisection

This page was built for publication: Spanning tree congestion and computation of generalized Győri-Lovász partition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5002702)