Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that $$c(\tau(a),\tau(1))+\sum_{i=1}^{a-1} c(\tau(i),\tau(i+1))\leq b $$ Prove this problem is NP-complete.

The NP-complete problems I have studied are SAT, nSAT, Hamiltonian path and partition sum. The problem looks like an Hamiltonian problem but I am not sure how to connect them. Can anyone give me a hint?

  • 2
    $\begingroup$ $c(i,j)$ can be viewed as a graph ajacency matrix with lengths of edges $c(i,j)$ and you need to find Hamiltonian path with length $\le b$ on it. Or what the $k$ stands for? $\endgroup$ – Alexey Burdin Apr 23 '15 at 23:45
  • $\begingroup$ @AlexeyBurdin sorry my bad. I've fixed it. What bother me most is the permutation $\tau$. What is the role it plays in here? $\endgroup$ – DDaren Apr 23 '15 at 23:50
  • 2
    $\begingroup$ $\tau$ is the order in which paths are visited $\tau(1)$ then $\tau(2)$ etc. You search over permutations $\tau$ of vertices to find the path. $\endgroup$ – kodlu Apr 24 '15 at 0:00
  • $\begingroup$ @kodlu Yes. Now I am thinking how to reduce Hamiltonian problem to this one. Adding length to each vertices? Find all Hamiltonian paths then count their lengths? Never done this kind of problem before. $\endgroup$ – DDaren Apr 24 '15 at 0:21
  • $\begingroup$ @DDaren, vertices above are $1\dots a$ or $\tau(1),\tau(2),\dots\tau(a)$ and the edges' lengths for are $c(i,j)$ for an edge from vertix $i$ to vertix $j$ $\endgroup$ – Alexey Burdin Apr 24 '15 at 1:25

Your Answer

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

Browse other questions tagged or ask your own question.