Hardness of some optimal oblivious routing generalizations

A generalization of the robust network design problem with oblivious routing is investigated in (Scutella', 2009), where the (uncertain) demands are served through two alternative routing templates. As indicated in that paper, it is an open issue as to whether the proposed problem, called (2-RND), is polynomially solvable or is NP-Hard. In this note we solve the issue by proving that (2-RND), as well as some generalizations, are NP-Hard. The hardness result holds true also when some routing templates are given as input data. This strengthens the results in (Scutella', 2009), where special (2-RND) cases are devised which are tractable from a computational perspective.