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.

翻译：我们研究以下称为最大鲁棒流（MRF）的基础网络优化问题：规划者在一个给定的有容量限制的网络中确定沿$s$-$t$路径的流。随后，一个对手从网络中移除$k$条弧，中断所有包含被移除弧的路径上的流。规划者的目标是在预期对手响应（即$k$条弧的最坏情况故障）下，最大化幸存流的值。长期以来已知，当$k = 1$时，MRF可在多项式时间内求解（Aneja等人，2001），而当$k$是输入的一部分时，该问题是$N\!P$-难的（Disser和Matuschke，2020）。然而，对于常数$k > 1$的情况，该问题的复杂性一直未得到解决，部分原因是自然线性规划描述的结构阻碍了优化与分离等价性的应用。本文引入一个归约，表明上述描述的基本MRF版本封装了看似更一般的变体，其中对手的选择被约束在网络弧的兼容性图中的$k$-团内。作为此归约的推论，我们能够证明以下结果：（1）对于任何常数$k > 1$的故障弧数，MRF是$N\!P$-难的。（2）当$k$是输入的一部分时，MRF是$P^{N\!P[\log]}$-难的。（3）MRF的整数版本是$Σ_2^P$-难的。