Approximation of Spanning Tree Congestion using Hereditary Bisection
Discrete Mathematics & Theoretical Computer Science · 12.06.2026 · vol. 28:2 (Graph Theory)
DOI: 10.46298/dmtcs.16997 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 12.06.2026. Verfasst von Petr Kolman.
Abstract (Originalsprache)
The Spanning Tree Congestion (STC) problem is the following NP-hard problem: given a graph $G$, construct a spanning tree $T$ of $G$ minimizing its maximum edge congestion where the congestion of an edge $e\in T$ is the number of edges $uv$ in $G$ such that the unique path between $u$ and $v$ in $T$ passes through $e$; the optimal value for a given graph $G$ is denoted $STC(G)$. It is known that every spanning tree is an $n/2$-approximation for the STP problem. A long-standing problem is to design a better approximation algorithm. Our contribution towards this goal is an $O(Δ\cdot\log^{3/2}n)$-approximation algorithm where $Δ$ is the maximum degree in $G$ and $n$ the number of vertices. For graphs with a maximum degree bounded by a polylog of the number of vertices, this is an exponential improvement over the previous best approximation. Our main tool for the algorithm is a new lower bound on the spanning tree congestion which is of independent interest. Denoting by $hb(G)$ the hereditary bisection of $G$ which is the maximum bisection width over all subgraphs of $G$, we prove that for every graph $G$, $STC(G)\geq Ω(hb(G)/Δ)$. Final DMTCS version. 9 pages
Zitieren
APA
Kolman, P. (2026). Approximation of Spanning Tree Congestion using Hereditary Bisection. Discrete Mathematics & Theoretical Computer Science, vol. 28:2(Graph Theory). https://doi.org/10.46298/dmtcs.16997
Vancouver
Kolman P. Approximation of Spanning Tree Congestion using Hereditary Bisection. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:2(Graph Theory). doi:10.46298/dmtcs.16997
BibTeX
@article{Kolman2026,
author = {Kolman, Petr},
title = {Approximation of Spanning Tree Congestion using Hereditary Bisection},
journal = {Discrete Mathematics & Theoretical Computer Science},
year = {2026},
volume = {vol. 28:2},
number = {Graph Theory},
doi = {10.46298/dmtcs.16997}
}
EUVIMED