Hardness of Robust Network Design

Free registration required

Executive Summary

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 this paper introduces a single-source version of the problem where the flow cut gap is known to be one. This paper 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.

  • Format: PDF
  • Size: 194.5 KB