An ss–tt connection problem with adaptability

We study a new two-stage version of an ss–tt path problem, which we call adaptable robust connection path (ARCP)  . Given an undirected graph G=(V,E)G=(V,E), two vertices s,t∈Vs,t∈V and two integers f,r∈Z+f,r∈Z+, ARCP asks to find a set S⊂ES⊂E of minimum cardinality which connects ss and tt, such that for any ‘failure set’ F⊂EF⊂E with |F|≤f|F|≤f, the set of edges S∖FS∖F can be completed to a set which connects ss and tt by adding at most rr edges from E∖FE∖F. We show the problem is NP-hard, and there is no polynomial-time αα-approximation algorithm for the problem for α<2α<2 unless P=NP. For f=r=1f=r=1 we provide an exact polynomial algorithm, and for f=1f=1 and arbitrary rr we provide a polynomial 2-approximation algorithm. A characterization of the feasible set is provided for f=1f=1 and several links are established between ARCP and other combinatorial optimization problems, including a new combinatorial optimization problem, the minimum reduced cost cycle problem whose complexity is open.