Hardness of robust network design

TLDR

The flow‑cut gap can be large in general graphs, complicating hardness proofs, and the single‑source version studied also subsumes fractional relaxations of spanning tree, Steiner tree, and shortest path problems. The authors introduce a single‑source version of the robust network design problem where the flow‑cut gap is known to be one. This formulation reduces the problem to a setting with a unit flow‑cut gap, simplifying the analysis. They prove that robust network design in undirected graphs is coNP‑hard, even for this single‑source version. © 2007 Wiley Periodicals, Inc., NETWORKS, Vol.

Abstract

Abstract The authors settle the complexity status of the robust network design problem in undirected graphs. The fact that the flow‐cut gap in general graphs can be large, poses some difficulty in establishing a hardness result. Instead, the authors introduce a single‐source version of the problem where the flow‐cut gap is known to be one. They then show that this restricted problem is coNP‐Hard. This version also captures, as special cases, the fractional relaxations of several problems including the spanning tree problem, the Steiner tree problem, and the shortest path problem. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 50–54 2007