2
$\begingroup$

I have a plane graph $G$ and a set of $k$ vertex pairs $\{s_1,t_1\}, \dots, \{s_k, t_k\}$. The goal is to find $k$ non-crossing paths connecting the pairs of terminals $s_i$ with $t_i$ in the graph so that the sum of path lengths is minimized. Note that the paths may "touch" each other, that is, share graph vertices and edges; the only requirement is that they do not cross.

It is easy to see that a solution always exists. Is finding an optimal solution NP-hard? I'm interested in the variant when $k$ is arbitrary and $G$ is a planar graph. However, the problem seems non-trivial even when $k=O(1)$ and/or $G$ is restricted. Say, is it possible to efficiently find such paths on a tree or a star?

An example of an input instance and a (possibly non-optimal) solution follows.

an instance with a solution

Most of the existing works (e.g., Shortest Non-Crossing Walks in the Plane) consider a similar problem in which the paths are not restricted to a graph and can be routed arbitrarily in the plane. In this setting, the terminals lie on obstacles and a solution might not exist. I'm not aware of a paper considering my variant of the problem.

Improve this question
$\endgroup$
3
  • $\begingroup$ The problem of steiner forest in planar graphs, that looks much easier to me, is NPC, so I would be surprised if this problem is not NPC. arxiv.org/pdf/0911.5143v1 $\endgroup$ – Sariel Har-Peled Nov 16 '15 at 16:36
  • $\begingroup$ @SarielHar-Peled: i also believe it's hard. The question is how to prove that :) $\endgroup$ – Sergey Pupyrev Nov 16 '15 at 23:05
  • $\begingroup$ Hmmm. Correctly? ;) $\endgroup$ – Sariel Har-Peled Nov 17 '15 at 4:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.