Approximation algorithms for network interdiction and fortification problems
Brian C. Dean, Adam Whitley · 2010
This dissertation discusses algorithms and results on several NP-hard graph problems which can all be classified as network interdiction and network fortification problems. The first problem studied, the multiway cut problem, is a generalization of the well-studied s-t min-cut problem, in which we must remove a minimum-cost subset of edges from a graph so that r > 2 designated terminals become disconnected from each other. We investigate an approximation algorithm for general r with a relatively simple analysis guaranteeing an approximation ratio ≤ 1.4647 − er, where er is a small constant related to the number of terminals r. This improves on the 1.5 – 1r guarantee of Caclinescu et al. [9] and is somewhat simpler than the 1.3438 − er result of Karger et al. [51]. We also perform three types of computational experiments to obtain empirical results and offer observations for the r = 4 case, based on small discretized instances. Next, we introduce a generalization of the multiway cut problem, called the k-hurdle multiway cut problem, in which every terminal-terminal path must be cut not merely once, but k > 1 times. We present a half-integrality proof implying a 2-approximation to the problem, a (1, k − 1)-pseudo approximation result, and also a true approximation algorithm with performance guarantee 2(1 − 1r ). This guarantee is unlikely to be improved upon, as we demonstrate an approximation-preserving reduction from the well-known vertex cover problem. A related problem we also study is the k-hurdle multicut problem, where we have a list of source-sink pairs (i, j), and each source must be separated from its sink kij times. We present a (log(n), cp1-3pkmaxc -pseudo approximation algorithm, with approximation guarantee O(log(n)) that guarantees all hurdles will be satisfied if all kij = O(1). We also obtain a 2-approximation for trees, which holds in both the standard k-hurdle multicut problem and a vertex variant, and we consider a hybrid problem of k-hurdle multiway cut and k-hurdle multicut, in which different hurdle counts kij exist between each pair of terminals (i, j), and all form an ultrametric. We demonstrate the half-integrality of this problem, implying a 2-approximation. Finally, we consider a problem called the network knapsack problem, which is a special case of a packing integer program where the underlying constraint system has a well-defined graph structure. We use dynamic programming to obtain a polynomial time solution on ladders of width k = O(1), and a polynomial time approximation scheme for trees and grids. We also investigate the difficulty of developing approximation algorithms for this problem on low-treewidth graphs and planar graphs.