1
$\begingroup$

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 ?

$\endgroup$
4
  • $\begingroup$ cs.stackexchange.com/q/142528/755 $\endgroup$
    – D.W.
    Aug 11 at 1:06
  • $\begingroup$ @D.W. I can not open this page in your comment. $\endgroup$ Aug 11 at 12:10
  • $\begingroup$ Should be back visible again. $\endgroup$
    – D.W.
    Aug 11 at 16:37
  • $\begingroup$ @D.W. Thank you, but i ask this question earlier, probably he/she is one of my classmates :) $\endgroup$ Aug 11 at 16:47
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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