2025/11/09 by Matuschke, Jannik
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2511.06505
We study the following fundamental network optimization problem known as Maximum Robust Flow (MRF): A planner determines a flow on s-t-paths in a given capacitated network. Then, an adversary removes k arcs from the network, interrupting all flow on paths containing a removed arc. The planner's goal is to maximize the value of the surviving flow, anticipating the adversary's response (i.e., a worst-case failure of k arcs). It has long been known that MRF can be solved in polynomial time when k = 1 (Aneja et al., 2001), whereas it is N P-hard when k is part of the input (Disser and Matuschke, 2020). However, the complexity of the problem for constant values of k > 1 has remained elusive, in part due to structure of the natural LP description preventing the use of the equivalence of optimization and separation. This paper introduces a reduction showing that the basic version of MRF described above encapsulates the seemingly much more general variant where the adversary's choices are constrained to k-cliques in a compatibility graph on the arcs of the network. As a consequence of this reduction, we are able to prove the following results: (1) MRF is N P-hard for any constant number k > 1 of failing arcs. (2) When k is part of the input, MRF is PN P[log]-hard. (3) The integer version of MRF is Σ2P-hard.