1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\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$ – Ilya Gazman Dec 10 '13 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 '13 at 18:50
  • $\begingroup$ Read this article, it says 2-opt is solution. $\endgroup$ – Ilya Gazman Dec 12 '13 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 '13 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$ – Ilya Gazman Dec 12 '13 at 12:45

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.