Rico Zenklusen, ETH Zurich
Abstract:
Network flow interdiction analysis studies by how much the value of a maximum flow in a network can be diminished by removing components of the network constrained to a fixed interdiction budget. Although the network interdiction problem is strongly NP-complete on general networks, pseudo-polynomial algorithms were found for planar networks with a single source and a single sink and without the possibility to remove vertices. These algorithms exploit planarity by transforming the problem into the planar dual of the original network.
In a first part of the talk an introduction into the network flow interdiction problem is given with a focus on pseudo-polynomial algorithms on planar graphs. Various extensions of current algorithms allowing to overcome some of the restrictions of previous methods are then proposed. In particular a planarity-preserving transformation is presented that allows to incorporate vertex removals and vertex capacities into pseudo-polynomial interdiction algorithms for planar graphs. Additionally, a pseudo-polynomial algorithm is introduced for determining the minimum interdiction budget needed to make it impossible to satisfy the demand of all sink nodes. The algorithm works on planar networks with multiple sources and sinks satisfying that the sum of the supplies at the source nodes equals the sum of the demands at the sink nodes.