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$.