On the complexity of resilient network design
Artur Tomaszewski, Michał Pióro, Mateusz Żotkiewicz · Networks · 2009
Abstract In this article we prove 𝒩𝒫‐hardness of two well‐known optimization problems related to the design of multicommodity flow networks with two different methods for providing network resiliency against failures: path diversity and flow restoration. Path diversity is a static mechanism that consists of using, for each demand, a number of paths and oversizing the flows assigned to these paths so that for any failure the total surviving flow is not less than the volume of the demand. By contrast, flow restoration is a dynamic mechanism that consists of reassigning the failed flows to backup paths when a failure occurs. Both mechanisms are of practical interest because although flow restoration is in general superior to path diversity in terms of the required amount of resource capacity, it might be too complicated to implement. By providing an appropriate reduction from the fractional graph coloring problem, we show that both problems are 𝒩𝒫‐hard in the general case of failure scenarios that admit simultaneous failures of multiple links. Finally, we discuss how to efficiently solve the two problems using path generation techniques. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010