# Minimum spanning tree with dynamic edge cost based on degrees

I have a problem that I'm struggling to solve or even name, I'd really appreciate any help or pointer to potential existing solutions.

Suppose there is a connected graph $$G$$ and we are trying to find a spanning tree $$M^*$$ with the following property. Let $$D_M(v)$$ be the degree of node $$v$$ in an arbitrary tree $$M$$. The solution $$M^*$$ satisfies:

$$M^* = \arg \min_M \sum_{(ij)\in M} C_{ij}$$ where $$C_{ij} = c_{ij} + f(D_M(i),D_M(j))$$ and is spanning ($$V\subset M$$).

Thus, this can be viewed as a "MST" where the cost of any edge depends on the degrees of the conneted nodes.

For the main case that I'm interested in, let

$$f = \beta \cdot \mathbf{1}\{\max(\text{deg}(i), \text{deg}(j)) > k \},$$

so there's essentially a cost $$\beta$$ for having an edge coming out of a node with more than $$k$$ connections. If I can solve this for $$k=2$$ I'd be very happy.

Added context: This problem is formulated to model a telecommunication network where the network planner tries to connect a hub to nodes. The cost $$\beta$$ captures "relay" cost: the network incurs $$\beta$$ if a path is split at a node (e.g. a Y-path would cost more than an L-path, all else equal). For intuition, $$\beta \to \infty$$ would eventually have the solution be a Hamiltonian path (as pointed out below, we only need $$\beta >> |V|$$. We want to solve this problem for a general $$\beta$$.

• Thanks! The problem is formulated from a practical problem. I added context. May 8 at 13:39
• Are there any bounds on the value of $\beta$? If not, then we can assume $\beta \gg |V|$. If yes, please state that. May 8 at 21:37
• $\beta$ is an exogenously given number, which could be any arbitrary value. Thanks for pointing out that $\beta >> |V|$ yields a special case! May 9 at 0:08

The Hamiltonian Path problem on undirected graphs can be reduced to your problem for $$k = 2$$ and $$\beta \gg |V|$$. Since the Hamiltonian Path problem is $$\mathsf{NP}$$-hard, your problem is $$\mathsf{NP}$$-hard as well.
For the proof of the above statement, you just need to observe the fact that if any spanning tree has all vertices of degree $$\leq2$$ then it is a hamiltonian path and vice-versa.
• Thanks, that makes sense. Unfortunately in the setting above we're interested in interior solutions where the network planner would like to trade off the number of splits (which incurs $\beta$) and the intrinsic edge cost ($c_{ij}$), so finding a Hamiltonian Path where there is no split would be too restrictive. May 8 at 13:47