10
$\begingroup$

Given a planar unweighted graph, and a collection of vertex pairs $(s,t_1),\dots,(s,t_k)$ ($k\ge2$ is a constant), find $k$ vertex-disjoint (except source) paths from $s$ to $t_i$ such that the length of the longest path is minimized.

Question: Is there a polynomial-time algorithm for the problem?

Some related results:

  • if $k$ is not fixed the problem is NP-hard even if $t_1=\dots=t_k$;
  • if the input graph is weighted and sources of paths do not coincide, i.e. paths are $(s_1,t_1),\dots,(s_k,t_k)$ the problem is NP-hard even for $k=2$;

  • a problem with different objective, namely minimizing the sum of path lengths, is

    • solvable with the minimum cost flow algorithm for coinciding sources;
    • NP-hard for non-coinciding sources and general $k$;
    • open for non-coinciding sources and constant $k$.
Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ It seems that there are many related results. Can you summarize important related results in the question? $\endgroup$
    – Tsuyoshi Ito
    Nov 22, 2011 at 16:00
  • $\begingroup$ Is the input graph G weighted (that is, each edge has a positive-integer length)? I had been assuming that G is not weighted, but I have realized that you are probably mixing up the two settings: (1) If G is weighted, then case of k=2 is NP-complete essentially by Theorem 14 in the paper by Kobayashi and Sommer which you linked to, which is also essentially the same as the last paragraph in Section 2 of [HP02] cited in my answer. (2) If G is not weighted, then I cannot see why the paper by Kobayashi and Sommer implies the NP-hardness in case of k=2 and different sources. $\endgroup$
    – Tsuyoshi Ito
    Nov 24, 2011 at 1:52
  • $\begingroup$ In my settings, a graph is not weighted, so you are right: my claim on NP-hardness in case of K=2 and different sources is (probably) wrong. $\endgroup$
    – Sergey Pupyrev
    Nov 24, 2011 at 4:37
  • $\begingroup$ I've updated the problem statement taking into account Tsuyoshi Ito's comment. $\endgroup$
    – Sergey Pupyrev
    Nov 24, 2011 at 6:13

1 Answer 1

Reset to default
6
$\begingroup$

This is not exactly what you asked, but the problem is NP-complete if k is not a constant but part of the input.

This follows from the proof of Theorem 1 in van der Holst and de Pina [HP02], which says: given a planar graph G, distinct vertices s and t in G, and positive integers k and b, it is NP-complete to decide whether there are k pairwise internally vertex-disjoint paths between s and t each of length at most b.

Note that the problem in the statement of Theorem 1 is different from yours in two respects. One difference is, as I mentioned, that k is given as part of the input. The other is that the problem in [HP02] is about paths with common endpoints instead of paths with a common source and different sinks. I do not know how to fix the first difference; the difference is so large that it is likely that we will need a completely different proof to fix k. But I know at least how to fix the second difference.

The proof of Theorem 1 in [HP02] gives a reduction from 3SAT. This reduction has the following property: in the instance (G, s, t, k, b) constructed by the reduction, the degree of vertex t is always equal to k. Let t1, …, tk be the k neighbors of t. Then instead of asking whether there are k pairwise internally vertex-disjoint paths between s and t each of length at most b, we can equally ask whether there are pairwise vertex-disjoint-except-source paths P1, …, Pk such that each Pi is a path between s and ti of length at most b−1.

[HP02] H. van der Holst and J. C. de Pina. Length-bounded disjoint paths in planar graphs. Discrete Applied Mathematics, 120(1–3):251–261, Aug. 2002. http://dx.doi.org/10.1016/S0166-218X%2801%2900294-3

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't see a big difference between your settings (when $k$ is given in the input) and my original settings (when $k$ vertex pairs are given). The problem with a common source and different sinks looks "harder" than the problem with the same source and sink. $\endgroup$
    – Sergey Pupyrev
    Nov 24, 2011 at 5:20
  • $\begingroup$ @SergeyPupyrev: You wrote that k is a constant. (You wrote it because you knew what it means, didn’t you?) From what I learned from a cursory look at relevant papers, whether k is a constant or not in related problems seems to make a huge difference in the current status of the complexity of the problem. $\endgroup$
    – Tsuyoshi Ito
    Nov 24, 2011 at 5:24
  • $\begingroup$ Let me clarify: your answer shows that if $k$ is not fixed then my original problem is NP-hard; otherwise, if $k$ is a constant then its complexity is unknown, right? $\endgroup$
    – Sergey Pupyrev
    Nov 24, 2011 at 5:39
  • 1
    $\begingroup$ @SergeyPupyrev: I cannot find a paper which states the complexity in the case where k is a constant, but this only means that it is unknown to me. $\endgroup$
    – Tsuyoshi Ito
    Nov 24, 2011 at 17:12

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.