MINIMUM ROUTING TREE CONGESTION

• INSTANCE: Graph $G=\left(V,E\right)$ and a weight function $w : E \rightarrow N$.

• SOLUTION: A routing tree T for G, i.e., a tree T in which each internal vertex has degree 3 and the leaves correspond to vertices of G.

• MEASURE: The congestion of the routing tree, i.e., the maximum, for any edge e, of
  
  $$\sum_{(u,v) \in E, u \in S, v \not\in S}w(u,v)$$
  
  
  where S is one of the two connected components obtained by deleting e from T.

  
  

• Good News: Approximable within $\log\vert V\vert$ [314].

• Bad News: Not in APX [436].

• Comment: The algorithm extends to the case when the routing tree is allowed to have vertices of higher degree. If G is planar [436], or if T is required to be a spanning tree and G is complete [314], the problem is solvable in polynomial time.