Interdiction in network maximum flow and related problems: A survey

In a network interdiction model, an attacker tries to maximize disruption to some network function (e.g., maximum flow, connectivity) by disabling/damaging certain network resources (e.g., nodes, arcs), and a defender tries to optimally cope with the above attack. Network interdiction problems w.r.t. maximum flow were first studied in the 1960s, mainly for their military and logistics applications. While early papers mostly presented non-polynomial time algorithms to identify the most valuable connections in a network, complexity and approximation results soon followed. In an increasingly networked society, interdiction has consistently remained a popular research topic to this day, with the initial formulation being supplemented by an impressive number of variants, and some derived problems, each tailored to the necessities of specific applications. This survey’s main focus is on providing a structured overview of the many variants of the max-flow interdiction problem that have emerged over the decades. Derived problems, such as robust flow assignments and vitality computation, are also discussed. Pointers to the techniques involved in achieving the most seminal results are presented as well. We conclude with a brief investigation into open directions to be explored in this rewarding research area.