# Spanning tree whose sum of edge weights are between two boundries

I saw this problem: $$\langle G,w,k_1,k_2 \rangle \in L$$ iff Graph $$G$$ has a spanning tree whose sum of edge wights are less than $$k_2$$ and greater than $$k_1$$. The problem says that we can prove this problem is NP-complete with reduction from Subset-Sum problem. First i cant see how is that possible. Second i know that we can solve Minimum Spanning Tree with kruskal , and i saw that we can compute Maximum Spanning Tree by negating the weights for each edge and applying Kruskal’s algorithm. So both of these problems can be solved in polynomial-time. But how this problem could not solved in polynomial-time ?

• cs.stackexchange.com/q/142528/755
– D.W.
Aug 11 at 1:06
• Should be back visible again.
– D.W.
Aug 11 at 16:37
• @D.W. Thank you, but i ask this question earlier, probably he/she is one of my classmates :) Aug 11 at 16:47

Let $$\langle S, t\rangle$$ be an instance of subset sum, where $$S = \{x_1, \dots, x_n\}$$, and $$t, x_1, \dots, x_n \in \mathbb{N}^+$$.

Create a graph $$G = (V,E)$$ where $$V = \{u,v\} \cup S$$ and $$E$$ contains:

• The edge $$(u,v)$$ of weight $$0$$.
• For each $$x_i \in S$$, an edge $$(u, x_i)$$ of weight $$x_i$$.
• For each $$x_i \in S$$, an edge $$(v, x_i)$$ of weight $$0$$.

There exists a spanning tree of $$G$$ of total weight between $$k_1 = t$$ and $$k_2 = t$$ (i.e., exactly $$t$$) if and only if $$\langle S, t \rangle$$ is a yes-instance of subset sum.

To see this let $$M$$ be the edges in a spanning tree $$T$$ of $$G$$ of weight $$w(T)=t$$ and define $$X = \{ x_i \mid (u, x_i) \in M \}$$. Clearly $$X \subseteq S$$ and $$\sum_{x_i \in X} x_i = w(T) = t$$.

Consider now a set $$X \subseteq S$$ such that $$\sum_{x_i \in X} x_i = t$$ and consider the set of edges $$M = \{ (u,x_i) \mid x_i \in S \} \cup \{ (v,x_i) \mid x_i \not\in S \} \cup \{(u,v)\}$$. It is easy to see that $$M$$ induces a tree of total cost $$t$$.

First of all, when we reduce problem $$A$$ to $$B$$ in polynomial time, we display it by $$A\le_p B$$, it's means that complexity of any algorithm for solving problem $$B$$ is at least hard as problem $$A$$. From this we act as follow:

Suppose you are Given un-dircted weighted graph $$G=(V,E,M,\omega)$$ with weight function $$\omega:E\to \mathbb{R}$$, and $$k_1=k_2=M$$. Then reduce finding spanning tree $$T$$ of $$G$$ to Integer programming as follow:

$$x_{ij} = \begin{cases} 1 & \text{if edge (i,j) in } T, \\ 0 & \text{otherwise.}\\ \end{cases}$$

$$\min 1$$

$$\text{S.t }\sum_{(i,j)\in T}x_{ij}=n-1$$ $$\sum_{(i,j)\in T}x_{ij}\omega(i,j)=M$$ $$x_{i,j}\in\{0,1\}$$

Now we formulate Subset-sum with problem as Integer programming as follow:

Suppose given numbers $$S=\{a_1,a_2,\dots,a_n\}$$, and target value $$M$$, the goal is to find a $$S'\subseteq S$$ :

$$x_{i} = \begin{cases} 1 & \text{if } a_i\text{ appear in solution}, \\ 0 & \text{otherwise.}\\ \end{cases}$$

$$\min 1$$

$$\text{S.t }\sum_{i\in S'}a_ix_i=M$$ $$x_{i}\in\{0,1\}$$

So, if we look at the above formulation of the two problems there are some relation between them. Now, i try to convert an instance of Subset-sum to spanning tree problem, to show that finding spanning tree at least hard as subset-sum.

Construct a graph $$G'$$ with $$n+1$$ vertices,and weight function $$\omega:E\to \mathbb{R}$$, and un-dircted edge set $$E$$ as follow:

$$V=\{s,a_1,a_2,\dots,a_n\}$$ $$E=\{(s,a_1),(s,a_2),\dots,(s,a_n)\}\cup\{(a_1,a_2),(a_2,a_3),\dots,(a_{n-1},a_n)\}.$$ Finally assign weight to each edge as follow $$\forall i\in\{1,2,\dots,n\}$$ $$\omega((s,a_i))=0,\omega((a_i,a_{i+1}))=a_i.$$

Clearly our reduction can be done in polynomial time in size of the input size. So if there is a algorithm $$\mathbb{A}$$ to find a spanning tree $$T$$ in $$G'$$ with $$\sum_{e\in T}\omega(e)=M$$ in polynomial time of the input size, then we solve subset-sum problem in poly time. As a result your mentioned problem is NP-complete.

Try to think what happens when $$k_1=k_2$$. It makes the question much more difficult.

In fact, consider the following reduction from subset sum: Say we have a set of numbers $$S=\{a_1,\dots,a_n\}$$ and a target value $$t$$. Let us choose $$k_1=k_2=t$$, and build the following graph $$G$$:

$$G$$ will have $$n+1$$ nodes: a special node will be called $$v$$, and another node $$u_i$$ for every $$1\le i\le n$$. We will put an edge between $$v$$ and $$u_i$$ with the cost of $$a_i$$, and another edge between $$v$$ and $$u_i$$ with a $$0$$ cost.

Finding a spanning tree $$T$$ in this case would be the same as choosing a subset $$A$$ of $$S$$, and the sum of the weights of $$T$$ will be the sum of the values in $$A$$. Hence, finding a spanning tree $$T$$ with weight sum equal to $$k_1=k_2=t$$ is equivalent to finding a subset $$A\subseteq S$$ with sum $$t$$.

Note: its not hard to do a similar reduction if you want the graph to be simple (i.e, every two nodes have at most one edge between them).