Computational Complexity of the Recoverable Robust Shortest Path Problem with Discrete Recourse
Provides tighter complexity bounds for a known robust optimization problem, of interest to researchers in combinatorial optimization and robust optimization.
The paper strengthens complexity results for the recoverable robust shortest path problem under discrete budgeted interval uncertainty, proving Sigma_3^p-hardness for arc exclusion and symmetric difference neighborhoods, and Pi_2^p-hardness for the inner adversarial problem.
In this paper the recoverable robust shortest path problem is investigated. Discrete budgeted interval uncertainty representation is used to model uncertain second-stage arc costs. The known complexity results for this problem are strengthened. It is shown that it is Sigma_3^p-hard for the arc exclusion and the arc symmetric difference neighborhoods. Furthermore, it is also proven that the inner adversarial problem for these neighborhoods is Pi_2^p-hard.