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?
1 Answer
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.
-
$\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$– EssamJan 29, 2021 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, 2021 at 12:39