0
$\begingroup$

If this is my adjacency matrix for the hamiltonian cycle: $$\begin{pmatrix}0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\end{pmatrix}$$ Then a reduction algorithm to reduce this to a TSP problem is to introduce 1 anywhere an edge is missing and let pre-existing edges have a cost of zero (according to this), applying this yields: $$\begin{pmatrix}1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\end{pmatrix}$$ Now I see that I have also introduced weighted-loops to my undirected graph, would asking whether this has a zero-cost salesman tour be equivalent to asking whether the unreduced version has a hamiltonian cycle, or should I maybe have something else on the diagonal of the reduced matrix?

$\endgroup$
2
$\begingroup$

Suppose your original graph $G$ has a Hamiltonian cycle $C$. Then the cost of the tour induced by $C$ in the new graph $G'$ you defined is indeed $0$ and conversely, any TSP tour of cost $0$ can only use edges of cost $0$ as you did not introduce any edges with a negative cost.

Adding the loops does not change this, so the reduction works out if we are willing to allow non-simple graphs which isn't done usually as the definition of the TSP asks for a tour visiting each vertex exactly once, i.e. no valid tour would include loop edges anyways. Given this, we also see that you can remove the loop edges in $G'$ to make it a simple graph to obtain an equally valid reduction. From a technical standpoint this doesn't make much of a difference but since people like simple graphs, I would personally prefer the reduction yielding a simple graph.

$\endgroup$
2
  • $\begingroup$ I would also prefer to reduce it to a simple graph, but I'm not sure then how should I represent the diagonal in my adjacency matrix. should I fill the diagonal with infinities? I mean you've already shown that it doesn't matter whether we have loops for the algorithm or not. But with the adjacency above, the algorithm is seeing the loops. $\endgroup$
    – Essam
    Jan 29 at 12:14
  • 1
    $\begingroup$ Well, this depends on how you represent non-existing edges in an adjacency (cost) matrix. I'm not sure that there is a standard way to do this. You could also just ditch adjacency matrices and choose some other equivalent representation like an adjacency list instead to eliminate the problem. $\endgroup$ Jan 29 at 12:39

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.