I have an Euclidean, undirected graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.

  • The number of vertices with no edges is small in comparison to the total number of vertices.
  • No vertex has more than two edges connected to it.

How can I convert this graph to a closed shape, so each vertex will have exactly two edges connected to it and there will be a path between any two vertices? I want to do it with minimum change in the total weight of all the edges.

  • $\begingroup$ Is your graph guaranteed to be planar or may edges cross? $\endgroup$ Oct 23, 2013 at 7:25
  • $\begingroup$ @reinierpost edges may cross $\endgroup$ Oct 23, 2013 at 7:30
  • $\begingroup$ So there are no paths of length 2 or more in the original graph? $\endgroup$ Oct 23, 2013 at 7:55
  • 1
    $\begingroup$ So you're looking for a cycle that contains all vertices? Maybe you want to start with a collection of cycles, 2-matchings are polytime solvable $\endgroup$
    – adrianN
    Oct 23, 2013 at 8:43
  • 1
    $\begingroup$ @Babidu: OK ... so it really is just a set of paths? $\endgroup$ Oct 23, 2013 at 16:29

1 Answer 1


This should be NP-hard, here's a way you could try to do a reduction:

Take any graph $G$ embedded in the $\mathbb{R}^2$ plane. Let $c_{min} = \min_{e \in E}\{c(e)\}$ be the minimum edge weight in the graph ($c$ is the weight function of the edges of $G$, i.e. the euclidean distance). To build $G'$, split every vertex $v = (x,y)$ into $v_1 = v$ and $v_2 = (x+\epsilon,y)$ where $\epsilon = \frac{c_{min}}{2^n}$, connect $v_1$ and $v_2$ with an edge weighted by their euclidean distance. Obviously, no vertex in $G'$ is incident with more than two edges, and there are no vertices that are incident with no edges.

What you now would have to prove is something like "there's a TSP route of weight $\le w$ in $G$ iff there's a TSP route of weight $\le w + n \cdot \epsilon$ in $G'$. I don't know how to prove that, but some geometry and use of the triangle inequality might help. I expect the choice of $\epsilon$ as vanishingly small will be enough to give the reduction.

EDIT: The reduction will remain valid after your edit.

  • $\begingroup$ Looking again on my old questions. There is a polynomial solution for this one with $O(n^4)$, 2-opt. If you be able to reduce it to NP-Complete problem it will be extremely interesting. $\endgroup$ Dec 10, 2013 at 7:52
  • $\begingroup$ As far as I'm aware (and I may be wrong), 2-opt is a heuristic, not a solution. $\endgroup$
    – G. Bach
    Dec 11, 2013 at 18:50
  • $\begingroup$ Read this article, it says 2-opt is solution. $\endgroup$ Dec 12, 2013 at 7:59
  • $\begingroup$ I couldn't find that it claimed anywhere that 2-opt is an exact solution instead of just an approximation algorithm, nor that it runs in polynomial time. $\endgroup$
    – G. Bach
    Dec 12, 2013 at 12:29
  • $\begingroup$ I probably didn't explain my self well. 2-opt does not solve the TSP it just run in polynomial time. $\endgroup$ Dec 12, 2013 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.