Computational Complexity of the Recoverable Robust Shortest Path Problem with Discrete Recourse
<|reference_start|>Computational Complexity of the Recoverable Robust Shortest Path Problem with Discrete Recourse: 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.<|reference_end|>
@article{jackiewicz2024computational,
    title={Computational Complexity of the Recoverable Robust Shortest Path Problem
  with Discrete Recourse},
    author={Marcel Jackiewicz, Adam Kasperski, Pawe{l} Zieli'nski},
    journal={arXiv preprint arXiv:2403.20000},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.20000},
    primaryClass={cs.CC}
}