Minimal cost linkages in graphs

In this paper, we consider the problem of finding minimal cost linkages in graphs. Wediscuss 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, weaddress 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) andMin‐Max Non‐Intersecting Paths (MMNP), and prove their NP‐completeness. We also showthat 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 link-agesmay only be defined over the r cheapest paths between each vertex pair. For fixedk >= 3, we show the restricted problems remain NP‐complete and discuss the limitations ofthe 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 optimisationproblem MSNP(r).