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.
|Autori:||C. CHEKURI; G.P. ORIOLO; SCUTELLA' M; F.B. SHEPHERD|
|Titolo:||Hardness of Robust Network Design|
|Anno del prodotto:||2007|
|Digital Object Identifier (DOI):||10.1002/net.20165|
|Appare nelle tipologie:||1.1 Articolo in rivista|