Static and Dynamic Routing Under Disjoint Dominant Extreme Demands

This paper considers the special case of the robust network design problem where the dominant extreme points of the demand polyhedron have a disjoint support. In this case static and dynamic routing lead to the same optimal solution, both for the splittable and the unspittable case. As a consequence, the robust network design problem with (splittable) dynamic routing is polynomially solvable, whereas it is coNP-Hard in the general case. This result applies to particular instances of the single-source Hose model.