A polynomial algorithm for the vertex disjoint Min-Min problem in planar graphs

Abstract

The Min-Min problem of finding a disjoint-path pair with the length of the shorter path minimized is known to be NP-hard in general graphs. However, it remains an open problem whether the Min-Min problem is NP-hard in some special graph such as planar graphs. In this paper, for an st-outerplanar graph G = (V,E) which is a special planar graph that can be drawn in the plane with source vertex s and destination vertex t belong to the unbounded face of the drawing, we show that the vertex disjoint Min-Min problem is polynomial solvable therein by presenting an algorithm with a time complexity of O(/E/ + /V/log/V/).