Hardness of Robust Network Design

We settle the complexity status of the robust network design problem by showing that a special case of the single-source hose model is coNP-Hard. This single-source model captures, as special cases, the fractional relaxations of several problems including the spanning tree problem, the Steiner tree problem, and the path trees problem.