# 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

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?

• $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? – Alexey Burdin Apr 23 '15 at 23:45
• @AlexeyBurdin sorry my bad. I've fixed it. What bother me most is the permutation $\tau$. What is the role it plays in here? – DDaren Apr 23 '15 at 23:50
• $\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. – kodlu Apr 24 '15 at 0:00
• @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. – DDaren Apr 24 '15 at 0:21
• @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$ – Alexey Burdin Apr 24 '15 at 1:25