I know how to find a pair of disjoint paths with the minimum sum of lengths (Surballe's algorithm). I also have a formulation of an ILP that solves the following problem, which generalizes my problem: Given two vertices u and v in a graph G, out of all of the disjoint pairs of paths connecting u and v in G, find a pair with the minimal length of the longer path in the pair. (Of course, this problem may be reformulated for groups of more than two disjoint paths).
Does anyone have an idea for an efficient (polynomial?) algorithm for solving any of these problems (The problem in the title or the generalized problem?)