<p>Let G be an undirected graph such that each edge e in G has a weight w(e). In addition, e has a profit p(e) where p(e) is in the set {1,2,...,n} (n being the number of vertices in G). Is finding a spanning tree of weight at most C with maximal profit NP-hard?</p>
<p>Without the profits, the problem is the classic MST problem which is polynomially solvable. However, are there works showing this variant of the MST problem NP-hard?</p>

CC BY-SA 4.0
2022-06-11T15:13:16.053Z
I think there's a polynomial-time algorithm for this. I'm pretty sure (but don't have a reference) that the problem of "given a graph $G=(V,E)$, edge weights $w(e)$, a partition $E=E_1\cup E_2$, and an integer $k$, compute a MST using exactly $k$ edges from $E_1$ if one exists" is efficiently solvable by doing some tricks with the usual MST algorithms. Run that algorithm with $E_1$ be the set with profits $1$ and $E_2$ with profits $2$ and each choice of $0\leq k\leq n$. Take the outputted tree for the smallest feasible value of $k$ whose MST has cost at most $C$.
Jason Gaitonde
CC BY-SA 4.0
2022-06-11T16:25:41.667Z
@JasonGaitonde Thanks!  I edited the question to a more general set of profits where your approach cannot be iterated in polynomial time. Does the problem becomes NP-hard now?
John
CC BY-SA 4.0
2022-06-11T17:20:20.040Z
"Constrained shortest paths" might be a useful search phrase for you.  This is the genre of problems where edges have both weights and costs, and you want an s-t path that minimizes total weight subject to cost below some given threshold.  Most problems of this type are NP hard.
GMB
CC BY-SA 4.0
2022-06-11T18:27:32.940Z
@John  It seems like it should be NP-hard, and certainly would be without the restriction that profits are at most $n$. But unfortunately one cannot do the obvious reduction from knapsack because the instance would need polynomially bounded weights, but knapsack with small weights is efficiently solvable...
Jason Gaitonde
CC BY-SA 4.0
2022-06-11T20:00:13.040Z
Problems with multiple weight functions are studied under the term "multiobjective optimization". For spanning trees two objective problem is known to be weakly NP-Hard. See https://link.springer.com/chapter/10.1007/3-540-61422-2_121.
Chandra Chekuri
CC BY-SA 4.0
2022-06-11T20:11:06.650Z
The problem admits a pseudo-polynomial time exact algorithm and a fully polynomial-time approximation scheme. For the specific case when the profits are are poly-bounded this should translate into a poly-time algorithm. See paper of Hassin and Levin and references therein. https://epubs.siam.org/doi/epdf/10.1137/S0097539703426775
Chandra Chekuri
CC BY-SA 4.0
2022-06-12T11:24:48.490Z
@ChandraChekuri This is very helpful. Thank you very much.
John
<spanning-tree>
Does the Minimum Spanning Tree (MST) problem become NP-hard when adding edge profits?
John
# Does the Minimum Spanning Tree (MST) problem become NP-hard when adding edge profits?

(Asked by: username_0 on 2022-06-11)

Let G be an undirected graph such that each edge e in G has a weight w(e). In addition, e has a profit p(e) where p(e) is in the set {1,2,...,n} (n being the number of vertices in G). Is finding a spanning tree of weight at most C with maximal profit NP-hard?

Without the profits, the problem is the classic MST problem which is polynomially solvable. However, are there works showing this variant of the MST problem NP-hard?

**Tags:** spanning-tree

> **Comments:**
> **username_1**: I think there's a polynomial-time algorithm for this. I'm pretty sure (but don't have a reference) that the problem of "given a graph $G=(V,E)$, edge weights $w(e)$, a partition $E=E_1\cup E_2$, and an integer $k$, compute a MST using exactly $k$ edges from $E_1$ if one exists" is efficiently solvable by doing some tricks with the usual MST algorithms. Run that algorithm with $E_1$ be the set with profits $1$ and $E_2$ with profits $2$ and each choice of $0\leq k\leq n$. Take the outputted tree for the smallest feasible value of $k$ whose MST has cost at most $C$.  
> **username_0**: @JasonGaitonde Thanks!  I edited the question to a more general set of profits where your approach cannot be iterated in polynomial time. Does the problem becomes NP-hard now?  
> **username_2**: "Constrained shortest paths" might be a useful search phrase for you.  This is the genre of problems where edges have both weights and costs, and you want an s-t path that minimizes total weight subject to cost below some given threshold.  Most problems of this type are NP hard.  
> **username_1**: @username_0  It seems like it should be NP-hard, and certainly would be without the restriction that profits are at most $n$. But unfortunately one cannot do the obvious reduction from knapsack because the instance would need polynomially bounded weights, but knapsack with small weights is efficiently solvable...  
> **username_3**: Problems with multiple weight functions are studied under the term "multiobjective optimization". For spanning trees two objective problem is known to be weakly NP-Hard. See https://link.springer.com/chapter/10.1007/3-540-61422-2_121.  
> **username_3**: The problem admits a pseudo-polynomial time exact algorithm and a fully polynomial-time approximation scheme. For the specific case when the profits are are poly-bounded this should translate into a poly-time algorithm. See paper of Hassin and Levin and references therein. https://epubs.siam.org/doi/epdf/10.1137/S0097539703426775  
> **username_0**: @ChandraChekuri This is very helpful. Thank you very much.  

---

## 0 answers

