In this paper, we consider the problem of finding minimal cost linkages in graphs. We discuss how this problem arises in practice and, in particular, its relevance to the military. Given a graph G with an associated cost function and a multiset of vertex pairs, we address the problem of finding a linkage of minimal cost. From this optimisation problem, we are able to define the decision problems Min–Sum Non-Intersecting Paths (MSNP) and Min–Max Non-Intersecting Paths (MMNP), and prove their NP-completeness. We also show that for fixed k ≥ 2, where k denotes the number of terminal pairs, MMNP remains NP-complete. We also define restricted versions of the problems, MMNP(r) and MSNP(r), where linkages may only be defined over the r cheapest paths between each vertex pair. For fixed r ≥ 3, we show the restricted problems remain NP-complete and discuss the limitations of the restriction. We include a case study which demonstrates the advantages of using heuristic methods, such as genetic algorithms and simulated annealing, to find solutions to the optimisation problem MSNP(r).
