2
$\begingroup$

Given a fully connected graph $G$, suppose that we are searching for a simple path $P$ with a specific cost $c$.

Is answering to that problem yes or no equivalent to subset-sum problem? What would be the complexity of finding such path?

I have made a reduction from subset-sum problem:

If each number in a set $S$ is a vertex of $G$ and weight of $<i,j>$ is $|i-j|$, then answering the question above yes or no is the same as solving the sumbet-sum problem.

P.S. The initial vertex I have visited is added to the cost.

Edit: Edge weights

$\endgroup$
  • $\begingroup$ What do you think? What have you tried? Also, the question is under-specified: Is the path allowed to repeat edges and/or nodes, or must it be a simple path? If you think the problem might be NP-complete, have you consulted a list of NP-complete problems and tried to find a reduction? If you think the problem might be in P, have you tried to come up with an algorithm? If you tried, what did you try and where did you get stuck? We expect you to do a significant amount of research before asking here, and to show us what you've tried in the question. $\endgroup$ – D.W. Apr 29 '14 at 18:15
  • $\begingroup$ If you have an answer for the question, please add this as an answer (yes, it's OK to answer your own question!) $\endgroup$ – Juho Apr 29 '14 at 18:28
  • $\begingroup$ I don't think your reduction works. If you take a path $(i,j,k)$, its weight will be $i+2j+k$, while you are aiming for $i+j+k$, I think. $\endgroup$ – FrankW Apr 29 '14 at 18:32
  • $\begingroup$ I have made some edits. I think now, it makes sense. $\endgroup$ – padawan Apr 29 '14 at 18:46
5
$\begingroup$

Given an instance $\langle \{s_1,\ldots,s_n\}, T \rangle$ of subset sum, construct the following weighted graph. The vertices are $$ v_0,v_1,\ldots,v_n,u_1,\ldots,u_n. $$ Connect $v_{i-1}$ and $v_i$ with an edge of weight $s_i$. Connect $v_{i-1}$ to $v_i$ via $u_i$ (i.e., add the edges $\{v_{i-1},u_i\},\{u_i,v_i\}$) with zero weight edges. There is a simple path of total cost $T$ iff there is a subset of $\{s_1,\ldots,s_n\}$ summing to $T$. This shows that your problem is NP-hard, and in fact NP-complete, since it's clearly in NP.

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