Finding min-max vertex-disjoint paths with a common source on planar graphs 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$.
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