Reserving resilient capacity in a network

We examine various problems concerning the reservation of capacity in a given network, where each arc has a per-unit cost, so as to be resilient against one or more arc failures. or a given pair (s, t) of nodes and demand T, we require that, on the failure of any k arcs of the network, there is sufficient reserved capacity in the remainder of the network to support an ( s, t) ow of value T. This problem can be solved in polynomial time for any fixed k, but we show that it is NP-hard if we are required to reserve an integer capacity on each arc. We concentrate on the case where the reservation has to consist of a collection of arc-disjoint paths: here we give a very simple algorithm to nd a minimum cost fractional solution, based on finding successive shortest paths in the network. Unlike traditional network ow problems, the integral version is NP-hard: we do, however, give a polynomial time 15/14-approximation algorithm in the case k = 1 and show that this bound is best possible unless P = NP.