MINIMUM DIAMETER SPANNING SUBGRAPH

• INSTANCE: Graph $G=\left(V,E\right)$, weight $w(e)\in Z^+$ and length $l(e)\in N$ for each $e\in E$, positive integer B.

• SOLUTION: A spanning subgraph $E'\subseteq E$ for G such that the sum of the weights of the edges in E' does not exceed B.

• MEASURE: The diameter of the spanning subgraph.

  
  

• Bad News: Not approximable within 2$-\varepsilon$ for any $\varepsilon >0$ [405].

• Comment: Not approximable within 3/2$-\varepsilon$ for planar graphs. Not approximable within 5/4$-\varepsilon$ if l(e)=1 for every edge e [405]. For results on minimum Steiner trees of bounded diameter, see MINIMUM STEINER TREE.

• Garey and Johnson: Similar to ND4