INOC2026

Abstract: The max–flow min–cut theorem links the maximum flow value

in a network to the capacity of the minimum s-t cut, with optimal

solutions corresponding to binary graph partitions. When arc ca-

pacities are uncertain, however, this integrality property may fail.

This paper studies robust max–flow and min–cut formulations

under uncertainty, with a focus on ellipsoidal uncertainty sets