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.
Hardness of Robust Network Design
SCUTELLA', MARIA GRAZIA;
2007-01-01
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.