Let G = (V, E) be a connected graph with specified vertex υ0 ∈ V, length l(e) ⩾ 0 for each e ∈ E, and positive parameters τ and γ. The cable-trench problem (CTP) is to find a spanning tree T such that τlτ(T) + γlγ(T) is minimized where lτ(T) is the total length of the spanning tree T and lγ(T) is the total path length in T from υ0 to all other vertices of V. Since all vertices must be connected to υ0 and only edges from E are allowed, the solution will not be a Steiner tree. Consider the ratio R = τ/γ. For R large enough the solution will be a minimum spanning tree and for R small enough the solution will be a shortest path. In this paper, the CTP will be shown to be NP-complete. A mathematical formulation for the CTP will be provided for specific values of τ and γ. Also, a heuristic will be discussed that will solve the CTP for all values of R.
