Two Complexity Results on Spanning-Tree Congestion Problems
arXiv:2601.10881v1 Announce Type: new Abstract: In the spanning-tree congestion problem ($mathsf{STC}$), we are given a graph $G$, and the objective is to compute a spanning tree of $G$ that minimizes the maximum edge congestion. While $mathsf{STC}$ is known to be $mathbb{NP}$-hard, even for some restricted graph classes, several key questions regarding its computational complexity remain open, and we address some of these in our paper. (i) For graphs of degree at most $d$, it is known that $mathsf{STC}$ […]