This thesis considers a Network Diversion Problem (NDP) in the directed graph, which is to identify a minimum cost set of links to cut so that any communications path from a designated source node to a destination node must include at least one link from a specified set, which is called the set of diversion arcs. We identify a redundant constraint from an earlier formulation. The problem is known to be NP-hard, however a detailed proof has not been given. We provide the proof of the NP-hardness of this problem. We develop a tabu search algorithm that includes a preprocessing procedure with two steps for removing diversion arcs as well as reducing the problem size. Computational results of the algorithm on instances of general graphs and grid graphs are reported.
