Online Supplement to \Sequential Grid Computing: Models and Computational Experiments"
Sam Ransbotham, Ishwar Murthy, Sabyasachi Mitra, Sridhar Narasimhan · 1990
Proof: The decision version of PS-K is defined on the same acyclic graph G(N,A) as for PS-1. Given a solution for which the answer is yes, its correctness can be verified in polynomial time; therefore, the problem belongs to NP. Li et al. (1990) introduced several versions of the Min Max Disjoint Path problem on a graph. One such version is: Given a directed graph G(N,A) with non-negative, integer arc lengths ci,j for each arc (i, j)∈A, determine K node disjoint paths between source node s and destination node t such that the length of the longest path is minimized. If G(N,A) allows cycles, this problem is strongly NP-Complete for K ≥ 2 (Li et al. 1990). If G(N,A) is acyclic, the problem is still NP-Complete for K ≥ 2, but a pseudo-polynomial algorithm exits. It therefore follows that on an acyclic graph, determining K ≥ 2 node disjoint paths between the first node 1 and the last node n such that the length of the shortest path among the K paths is maximized is also NP-Complete. We refer to this problem as MaxMinD-K. Given a threshold length T , the decision version of MaxMinD-K is: Do there exist K node disjoint paths in G(N,A) from node 1 to node n such that the length of the shortest path among the K paths is at least T? We now proceed to show that the decision version of MaxMinD-K reduces to an instance of the decision version of PS-K. Any acyclic graph G(N1,A1) on which MaxMinD-K is defined can be