Id: arxiv/2602.01360 Url: https://arxiv.org/abs/2602.01360 Tags: math.OC Score: 0 Title: Minimum cost network flow with interval capacities: The worst-case scenario Domain: math.OC Source: arxiv Authors: Miroslav Rada, Milan Hladík, Elif Radová Garajová, Francesco Carrabs, Raffaele Cerulli, Ciriaco D'Ambrosio Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-01 Page: https://delphi.science/r/arxiv/2602.01360 We study the problem of determining the worst optimal value and characterizing the corresponding worst-case scenarios in minimum cost network flow problems with interval uncertainty in arc capacities. In this setting, each capacity can take any value within its specified lower and upper bounds. We prove that computing the worst optimal value is a strongly NP-hard problem and remains NP-hard even when restricted to series-parallel graphs. Further, we propose a mixed-integer linear programming formulation that computes the exact worst optimal value, as well as a pseudopolynomial-time algorithm…