The maximum residual flow problem:NP‐hardness with two‐arc destruction
Donglei Du, R. Chandrasekaran · Networks · 2007
Abstract The maximum residual flow problem with one‐arc destruction is shown to be solvable in strongly polynomial time in [Aneja et al., Networks, 38 (2001), 194–198]. However, the status of the corresponding problem with more than one‐arc destruction is left open therein. We resolve the status of the two‐arc destruction problem by demonstrating that it is already NP‐hard. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(3), 181–182 2007