text: The well-known @math -disjoint path problem ( @math -DPP) asks for pairwise vertex-disjoint paths between @math specified pairs of vertices @math in a given graph, if they exist. The decision version of the shortest @math -DPP asks for the length of the shortest (in terms of total length) such paths. Similarly the search and counting versions ask for one such and the number of such shortest set of paths, respectively. We restrict attention to the shortest @math -DPP instances on undirected planar graphs where all sources and sinks lie on a single face or on a pair of faces. We provide efficient sequential and parallel algorithms for the search versions of the problem answering one of the main open questions raised by Colin de Verdiere and Schrijver for the general one-face problem. We do so by providing a randomised @math algorithm along with an @math time randomised sequential algorithm. We also obtain deterministic algorithms with similar resource bounds for the counting and search versions. In contrast, previously, only the sequential complexity of decision and search versions of the "well-ordered" case has been studied. For the one-face case, sequential versions of our routines have better running times for constantly many terminals. In addition, the earlier best known sequential algorithms (e.g. ) were randomised while ours are also deterministic. The algorithms are based on a bijection between a shortest @math -tuple of disjoint paths in the given graph and cycle covers in a related digraph. This allows us to non-trivially modify established techniques relating counting cycle covers to the determinant. We further need to do a controlled inclusion-exclusion to produce a polynomial sum of determinants such that all "bad" cycle covers cancel out in the sum allowing us to count "good" cycle covers.
  @cite_29: The following problem is considered: given: an undirected planar graph G = (V,E) embedded in R2, distinct pairs of vertices r1,s1 ..... rk,sk of G adjacent to the unbounded face, positive integers b1,... ,bk and a function l : E → Z+; find: pairwise vertex-disjoint paths P1,...,Pk such that for each i = 1,...,k, Pi is a ri-si-path and the sum of the l-length of all edges in Pi is at most bi. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k = 2.
  @cite_2: Given an undirected graph and two pairs of vertices (s i ,t i ) for i ∈ 1,2 we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining s i and t i for i ∈ 1,2 respectively, or concludes that there most likely are no such paths at all. Our algorithm applies to both the vertex- and edge-disjoint versions of the problem.
summary: The optimization problem is considerably harder. A version of the problem, called DPP, where the each of the path need to have length bounded by some integer @math . This problem is -hard in the strong sense even in the One-face case for non-fixed @math @cite_29 . For the shortest @math -DPP, where we want to minimise the sum of the lengths of the paths, very few instances are known to be solvable in polynomial time. For general undirected graphs, very recently, Bj " o rklund and Husfeldt @cite_2 have shown that shortest @math -DPP admits a randomised polynomial time algorithm. The deterministic polynomial time bound for the same – to this date – remains an intriguing open question.