2
$\begingroup$

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$.

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – quanecon
    May 8 at 13:47
  • $\begingroup$ @quanecon Aren't you looking for a spanning tree: connected graph that spans all vertices? $\endgroup$
    – Inuyasha Yagami
    May 8 at 14:11
  • $\begingroup$ Yes! A spanning tree, where there are penalties for "splits". I added that wording. Thanks. $\endgroup$
    – quanecon
    May 8 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.