Spanning tree congestion of proper interval graphs
arXiv:2602.13756
summary
The paper proves that the spanning tree congestion problem is NP‑complete even on proper interval graphs with linear clique‑width at most 4 and diameter 3, and extends the hardness to general graphs of diameter 2.
Abstract
We show that the spanning tree congestion problem is NP-complete even on proper interval graphs with linear clique-width at most 4 and diameter 3. By slightly modifying the reduction, we also show that the problem is NP-complete on (general) graphs of diameter 2.
14 pages, 3 figures
Topics & keywords
#spanning tree congestion#proper interval graphs#np-completeness#graph diameter#clique-widthspanning tree congestionproper interval graphsNP-completelinear clique-widthgraph diameter