Better Hardness Results for the Minimum Spanning Tree Congestion Problem

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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mi>P</mml:mi> </mml:mrow> </mml:math> -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}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> <mml:mo>-</mml:mo> <mml:mi>STC</mml:mi> </mml:mrow> </mml:math> , we need to determine if G has a spanning tree with congestion at most K . It is known that $${\varvec{K}-\textsf {STC}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> <mml:mo>-</mml:mo> <mml:mi>STC</mml:mi> </mml:mrow> </mml:math> is $$\mathbb{N}\mathbb{P}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mi>P</mml:mi> </mml:mrow> </mml:math> -complete for $$K\ge 8$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>8</mml:mn> </mml:mrow> </mml:math> , and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand, $${\varvec{3}-\textsf {STC}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> <mml:mo>-</mml:mo> <mml:mi>STC</mml:mi> </mml:mrow> </mml:math> can be solved in polynomial time, with the complexity status of this problem for $$K\in { \left\{ 4,5,6,7 \right\} }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>∈</mml:mo> <mml:mfenced> <mml:mn>4</mml:mn> <mml:mo>,</mml:mo> <mml:mn>5</mml:mn> <mml:mo>,</mml:mo> <mml:mn>6</mml:mn> <mml:mo>,</mml:mo> <mml:mn>7</mml:mn> </mml:mfenced> </mml:mrow> </mml:math> remaining an open problem. We substantially improve the earlier hardness results by proving that $${\varvec{K}-\textsf {STC}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> <mml:mo>-</mml:mo> <mml:mi>STC</mml:mi> </mml:mrow> </mml:math> is $$\mathbb{N}\mathbb{P}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mi>P</mml:mi> </mml:mrow> </mml:math> -complete for $$K\ge 5$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> </mml:math> . This leaves only the case $$K=4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>=</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> 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}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> <mml:mo>-</mml:mo> <mml:mi>STC</mml:mi> </mml:mrow> </mml:math> restricted to graphs of radius 2, and we