We study the computational complexity of determining the spanning tree congestion of a graph. First, we show that the problem of determining whether a given graph has spanning tree congestion at most fixed k can be solved in linear time for graphs of bounded degree. Next, we show that the problem becomes NP-complete for every fixed k ≥ 10 if we allow only one vertex of unbounded degree in the input graphs. We also show that it is NP-hard to approximate the spanning tree congestion of such graphs within a factor better than 11/10.
展开▼
