# Cyclic tour minimizing total weight

I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant.

I saw the question below on an old stack exchange question when looking to understand NP-completeness. At first, I thought I understood it so I gave it a go but ended up more confused than before (I'm a maths student and computational complexity is my first foray into CS and I'm struggling to get to grips with it).

Question is as below:

Given as inputs integers $$a, b$$ and $$c(i,j)$$ for each $$i,j \leq a$$, decide if there is a permutation $$\tau$$ of $$\{1,2,\dots,a\}$$ 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. Hint: find a reduction from the Hamiltonian circuit decision problem (given a graph, decide whether it contains a Hamiltonian circuit).

It seems very similar to the decision version of TSP (where given a set of cities with the distances between each pair of cities, and a length $$k$$, does there exist a circuit connecting all cities of length less than $$k$$). I've read the proof for NP-completeness of TSP and I feel like I understand the reduction from Hamiltonian circuit decision problem to TSP, but I can't get it to translate into a reduction from HC to this problem.

My understanding to compare this to TSP, is that $$a$$ is the number of cities, each $$c(i,j)$$ represents the distance between city $$i$$ and $$j$$.

My (fairly poor) attempt at this reduction is as follows;

The problem is clearly in NP as we can non-deterministically "guess" a permutation and calculate the given sum and verify that it's at most $$b$$ in polynomial time.

Then, given a graph $$G=\langle V,E\rangle$$ where there are $$a$$ vertices, say $$1,2,\ldots,a$$, and $$b$$ edges of length $$c(i,j)$$, where $$i \neq j$$ and $$i,j\leq a$$, construct the completion of $$G'$$ of $$G$$ and a weight function that assigns any edge of $$G'$$ a 1 if the edge is present in $$G$$ and 2 if not. This can be computed in polynomial time.

Then if $$G$$ contains a Hamiltonian circuit (consisting of $$b$$ edges), this path has weight at most $$b$$ in $$G'$$ and so the sum of the lengths of this path is at most $$b$$ and so the permutation corresponding to the order of this path satisfies the original decision problem for these numbers $$a,b$$ and $$c(i,j)$$.

Conversely, if given the numbers $$a,b$$ and $$c(i,j)$$ and a permutation $$\tau$$ that satisfy the problem the associated graph G contains a path starting at $$\tau(a)$$ and finishing at $$\tau(b)$$. Thus G has a Hamiltonian circuit.

Thus HC reduces to this problem and hence it is NP-hard and so NP-complete.

I can tell it's wrong but I'm not sure how to properly describe a function relating to Hamiltonian circuits and lengths into weights in $$G'$$.

Any advice and or pointers would be much appreciated.

Usually we consider metric versions of TSP, in which the triangle inequality $$c(i,k) \leq c(i,j) + c(j,k)$$ holds, and often the TSP instance is symmetric, $$c(i,j) = c(j,i)$$. Your reduction shows that (symmetric) metric TSP is also NP-complete, since the cost function you construct is symmetric and satisfies the triangle inequality.