The cable trench problem: combining the shortest path and minimum spanning tree problems

Let G=(V,E) be a connected graph with specified vertex v0∈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 v0 to all other vertices of V. Since all vertices must be connected to v0 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.