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$
    – user7329
    Nov 24, 2011 at 4:37
  • $\begingroup$ I've updated the problem statement taking into account Tsuyoshi Ito's comment. $\endgroup$
    – user7329
    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$
    – user7329
    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$
    – user7329
    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 and acknowledge that you have read and understand our privacy policy and code of conduct.