Finding Two Disjoint Paths in a Network with Min-Min Objective Function

摘要

Given a network G = (V, E) and two nodes s and t in G, we consider the problem of finding two disjoint paths from s to t such that the length of the shorter path is minimized. The paths may be node-disjoint or edge-disjoint, and the network may be directed or undirected. This problem has applications in reliable communication. We show that all four versions of this problem are NP-complete and polynomial-time approximation algorithms for obtaining solutions with bounded error are impossible unless P = NP. We also show that all four versions of this problem are NP-complete and polynomial-time approximation algorithms for obtaining solutions with bounded error are impossible unless P = NP even when all edges have the same length. For a special case of this problem, we give a polynomial-time algorithm for finding optimal solutions.