2026-07-22T06:28:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22888 2025-10-02T13:36:33Z ddc:004 open_access

Approximation of Spanning Tree Congestion Using Hereditary Bisection Kolman, Petr Spanning Tree Congestion Bisection Expansion Divide and Conquer 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 ∈ 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 STC problem. A long-standing problem is to design a better approximation algorithm. Our contribution towards this goal is an 𝒪(Δ⋅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) ≥ Ω(hb(G)/Δ). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petr Kolman 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.63 urn:nbn:de:0030-drops-228880 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.63 eng https://creativecommons.org/licenses/by/4.0/legalcode