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

Original language | English |
---|---|

Pages (from-to) | 641-653 |

Number of pages | 13 |

Journal | Algorithmica |

Volume | 66 |

Issue number | 3 |

DOIs | |

Publication status | Published - Jul 2013 |

Externally published | Yes |

## Keywords

- Disjoint paths
- Min-Min problem
- NP-hardness
- Planar graph
- Polynomial-time algorithm
- Shortest path