Stronger Hardness for Maximum Robust Flow and Randomized Network Interdiction Article Swipe

MAKE IMPACT

Matuschke, Jannik · YOU? · · 2025 · Open Access ·

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 $Σ_2^P$-hard.

Type

article

Landing Page

http://arxiv.org/abs/2511.06505

PDF

https://arxiv.org/pdf/2511.06505

OA Status

green

OpenAlex ID

https://openalex.org/W7105506048

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W7105506048

Canonical identifier for this work in OpenAlex

Title

Stronger Hardness for Maximum Robust Flow and Randomized Network Interdiction

Work title

Type

article

OpenAlex work type

Publication year

2025

Year of publication

Publication date

2025-11-09

Full publication date if available

Authors

Matuschke, Jannik

List of authors in order

Landing page

https://arxiv.org/abs/2511.06505

Publisher landing page

PDF URL

https://arxiv.org/pdf/2511.06505

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2511.06505

Direct OA link when available

Concepts

Mathematics, Mathematical optimization, Flow network, Equivalence (formal languages), Time complexity, Constant (computer programming), Maximum flow problem, Robustness (evolution), Flow (mathematics), Minification, Algorithm, Interdiction, Minimum-cost flow problem, Computational complexity theory, Reduction (mathematics), Linear programming, Graph, Integer programming, Minimum cut, Theory of computation, Optimization problem, Polynomial, Robust optimization, Bernoulli's principle, Computer science

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Full payload