Please tell me if my next optimization can work:

I have symmetric, weighted, undirected graph, where it is knowen that the optimal tour, that visit all the vertices exactly once and return to the starting vertex, only contains edges with the weight of 1, it is also known that there is no edge with weight less than 1.

My goal is to find that tour.

Within this graph I want to look in to the case where there's a node, $B$ with only two edges with weight of 1 connected to it, let's call them, $AB$ and $BC$. I know that $AB,BC$ must be part of the optimal tour because there is no other way to get to $B$ and from $B$ with weight of 1. So I am removing the node $B$ and adding extra edge $AC$ between the endpoints of the removed node, and I am giving it the weight 0. Now when I find the optimal tour of that new graph(I assume that $AC$ will be part of it), I will replace it back to $AB,BC$, and I believe it will be the optimal tour of my original graph.

Do you think it will work?

  • $\begingroup$ 1. What do you mean by "symmetric graph"? 2. If you know that there are no 2 edges in the optimum, why not simply remove all of them? Are you trying to approximate the optimum? $\endgroup$ – Shaull Nov 4 '13 at 9:12
  • $\begingroup$ @Shaull edited. I can't just remove edges. I am solving TSP, all the nodes connected between them self by definition. $\endgroup$ – Ilya Gazman Nov 4 '13 at 10:44
  • 1
    $\begingroup$ so essentially you are proposing a heuristic to solve the Hamiltonian circuit problem - since you assume edges of cost 2 are not in the cycle, you can consider the graph without them, and then you are searching for a Hamiltonian cycle. What you're saying is that you don't know how to extend the heuristic when you have a vertex of degree more than 2. There are many ways to extend it, none of them are likely to give you a good approximation. $\endgroup$ – Shaull Nov 4 '13 at 10:58
  • $\begingroup$ @Shaull Actually its Hamiltonian circuit reduced to TSP. I do not assume that edges of cost 2 are not in the cycle, I know this by definition of the reduction. I do not expect to find the optimal tour from my optimization but an easier to solve TSP. $\endgroup$ – Ilya Gazman Nov 4 '13 at 11:20
  • 1
    $\begingroup$ Well, it is unlikely that you will be able to do something simple like replacing a node with a polynomial number of edges, since this would give a polynomial time algorithm for TSP. $\endgroup$ – Shaull Nov 4 '13 at 12:56

Since your TSP tour needs to visit all nodes but not all edges, replacing nodes by edges is dangerous, even in the case of degree 2 nodes. You can of course replace a node by a clique on its neighbors, but you need to add a mechanism that ensures that at least one of the edges of the clique is taken.


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.