Spanning tree whose sum of edge weights are between two boundries

Question

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 ?

Answer 1

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

Answer 2

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.

Answer 3

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