Max-flow min-cut theorem and faster algorithms in a circular disk failure model

Abstract

Fault-tolerance is one of the most important factors in designing networks. Failures in networks are sometimes caused by an event occurring in specific geographical regions such as hurricanes, earthquakes, bomb attacks, and Electromagnetic Pulse (EMP) attacks. In INFOCOM 2012, Neumayer et al. introduced geographical variants of max-flow min-cut problems in a circular disk failure model, in which each failure is represented by a disk with a predetermined size. In this paper, we solve two open problems in this model: we give a first polynomial-time algorithm for the geographic max-flow problem, and prove a conjecture of Neumayer et al. on a relationship between the geographic max-flow and the geographic min-cut.