SCIENCE@home

Stronger Hardness for Maximum Robust Flow and Randomized Network Interdiction

J. Matuschke

Published 2025 in arXiv.org

ABSTRACT

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 $P^{N\!P[\log]}$-hard. (3) The integer version of MRF is $\Sigma_2^P$-hard.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-28 of 28 references · Page 1 of 1

CITED BY

  • No citing papers are available for this paper.

Showing 0-0 of 0 citing papers · Page 1 of 1