The Min‐Min problem of finding a disjoint‐path pair with the length of the shorter path minimized is known to be NP‐hard and admits no K‐approximation for any K>1 in the general case (Xu et al. in IEEE/ACM Trans. Netw. 14:147–158, 2006). In this paper, we first show that Bhatia et al.’s NP‐hardness proof (Bhatia et al. in J. Comb. Optim. 12:83–96, 2006), a claim of correction to Xu et al.’s proof (Xu et al. in IEEE/ACM Trans. Netw. 14:147–158, 2006), for the edge‐disjoint Min‐Min problem in the general undirected graphs is incorrect by giving a counter example that is an unsatisfiable 3SAT instance but classified as a satisfiable 3SAT instance in the proof of Bhatia et al. (J. Comb. Optim. 12:83–96, 2006). We then gave a correct proof of NP‐hardness of this problem in undirected graphs. Finally we give a polynomial‐time algorithm for the vertex disjoint Min‐Min problem in planar graphs by showing that the vertex disjoint Min‐Min problem is polynomially solvable in st‐planar graph G=(V,E) whose corresponding auxiliary graph G(V,E∪{e(st)}) can be embedded into a plane, and a planar graph can be decomposed into several st‐planar graphs whose Min‐Min paths collectively contain a Min‐Min disjoint‐path pair between s and t in the original graph G. To the best of our knowledge, these are the first polynomial algorithms for the Min‐Min problems in planar graphs.
