2022/09/17 by Luu, Huong, Chrobak, Marek
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2209.08219
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 \mathbbNP-hard, but its approximability is still poorly understood. In the decision version of this problem, denoted K-\textsfSTC, we need to determine if G has a spanning tree with congestion at most K. It is known that K-\textsfSTC is \mathbbNP-complete for K≥ 8. On the other hand, 3-\textsfSTC can be solved in polynomial time, with the complexity status of this problem for K∈ \4,5,6,7\ remaining an open problem. We substantially improve the earlier hardness results by proving that K-\textsfSTC is \mathbbNP-complete for K≥ 5. This leaves only the case 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 consider K-\textsfSTC restricted to graphs of radius 2, and we prove that this variant is \mathbbNP-complete for all K≥ 6. Exploring further in this direction, we also examine the variant, denoted K-\textsfSTCD, where the objective is to determine if the graph has a depth-D spanning three of congestion at most K. We prove that 6-\textsfSTC2 is \mathbbNP-complete even for bipartite graphs. For bipartite graphs we establish a tight bound, by also proving that 5-\textsfSTC2 is polynomial-time solvable. Additionally, we complement this result with polynomial-time algorithms for two special cases that involve bipartite graphs and restrictions on vertex degrees.