1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

The problem you describe is exactly asymmetric TSP. As your reduction shows, asymmetric TSP generalizes the Hamiltonian circuit problem, which is known to be NP-hard.

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.

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