Abstract In the spanning tree congestion problem, given a connected graph G , the objective is to compute a spanning tree T in G that minimizes its maximum edge congestion, where the congestion of an edge e of T is the number of edges in G for which the unique path in T between their endpoints traverses e . The problem is known to be $$\mathbb{N}\mathbb{P}$$ N P -hard, but its approximability is still poorly understood, and it is not even known whether the optimum solution can be efficiently approximated with ratio o ( n ). In the decision version of this problem, denoted $${\varvec{K}-\textsf {STC}}$$ K - STC , we need to determine if G has a spanning tree with congestion at most K . It is known that $${\varvec{K}-\textsf {STC}}$$ K - STC is $$\mathbb{N}\mathbb{P}$$ N P -complete for $$K\ge 8$$ K ≥ 8 , and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand, $${\varvec{3}-\textsf {STC}}$$ 3 - STC can be solved in polynomial time, with the complexity status of this problem for $$K\in { \left\{ 4,5,6,7 \right\} }$$ K ∈ 4 , 5 , 6 , 7 remaining an open problem. We substantially improve the earlier hardness results by proving that $${\varvec{K}-\textsf {STC}}$$ K - STC is $$\mathbb{N}\mathbb{P}$$ N P -complete for $$K\ge 5$$ K ≥ 5 . This leaves only the case $$K=4$$ K = 4 open, and improves the lower bound on the approximation ratio to 1.2. Motivated by evidence that minimizing congestion is hard even for graphs of small constant radius, we also consider $${\varvec{K}-\textsf {STC}}$$ K - STC restricted to graphs of radius 2, and we