2024/10/01 by Kolman, Petr
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2410.00568
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 STP problem. A long-standing problem is to design a better approximation algorithm. Our contribution towards this goal is an O(Δ⋅log3/2n)-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)/Δ).