Bounded Diameter Spanning Tree

Input

Graph $G = (V, E)$, weight $w(e) \in \mathbb{Z}^{+}$ for each $e \in E$, positive integer $D \leq |V|$, positive integer $B$.

Question

Is there a spanning tree $T$ for $G$ such that the sum of the weights of the edges in $T$ does not exceed $B$ and such that $T$ contains no simple path with more than $D$ edges?

Classes

• NP-complete

Comments

Remains NP-complete for any fixed $D \geq 4$, even if all edge weights are either 1 or 2. Can be solved easily in polynomial time if $D \leq 3$, or if all edge weights are equal.

Proofs

NP-complete

Transformation from Exact Cover by 3-Sets (Garey & Johnson, 1979).

Reducible from

• Exact Cover by 3-Sets

References

• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.