The Complexity Classes of Hamming Distance Recoverable Robust Problems

The well-known complexity class NP contains combinatorial problems, whose optimization counterparts are important for many practical settings. In reality, however, uncertainty in the input data is a usual phenomenon, which is typically not covered in NP problems. One concept to model the uncertainty in the input data, is recoverable robustness. The instance of the recoverable robust version of a combinatorial problem P is split into a base scenario \(\sigma _0\) and an uncertainty scenario set \(\textsf {S}\) . The task is to calculate a solution \(\texttt {s}_0\) for the base scenario \(\sigma _0\) and solutions \(\texttt {s}\) for all uncertainty scenarios \(\sigma \in \textsf {S}\) such that \(\texttt {s}_0\) and \(\texttt {s}\) are not too far away from each other according to a distance measure, so \(\texttt {s}_0\) can be easily adapted to \(\texttt {s}\) . We analyze the complexity of Hamming distance recoverable robust versions of problems in NP for different scenario encodings. The complexity is primarily situated in the lower levels of the polynomial hierarchy. The main contribution of the paper is a gadget reduction framework that reveals that the recoverable robust version of problems in a large class of combinatorial problems is \(\varSigma ^p_{3}\) -complete. We show that this class includes over 20 problems such as Vertex Cover, Independent Set, Hamiltonian Path or Subset Sum. We expect that the number of problems can be easily extended with the help of the gadget reduction framework. Additionally, we expand the results to \(\varSigma ^p_{2m+1}\) -completeness for multi-stage recoverable robust problems with \(m \in \mathbb {N}\) stages.