Converting graphs to sets of paths

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.

• Is your graph guaranteed to be planar or may edges cross? – reinierpost Oct 23 '13 at 7:25
• @reinierpost edges may cross – Ilya Gazman Oct 23 '13 at 7:30
• So there are no paths of length 2 or more in the original graph? – reinierpost Oct 23 '13 at 7:55
• 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 – adrianN Oct 23 '13 at 8:43
• @Babidu: OK ... so it really is just a set of paths? – reinierpost Oct 23 '13 at 16:29

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.

• 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. – Ilya Gazman Dec 10 '13 at 7:52
• As far as I'm aware (and I may be wrong), 2-opt is a heuristic, not a solution. – G. Bach Dec 11 '13 at 18:50
• Read this article, it says 2-opt is solution. – Ilya Gazman Dec 12 '13 at 7:59
• 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. – G. Bach Dec 12 '13 at 12:29
• I probably didn't explain my self well. 2-opt does not solve the TSP it just run in polynomial time. – Ilya Gazman Dec 12 '13 at 12:45