Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization

In bilevel and robust optimization we are concerned with combinatorial min-max problems, for example from the areas of min-max regret robust optimization, network interdiction, most vital vertex problems, blocker problems, and two-stage adjustable robust optimization. Even though these areas are well-researched for over two decades and one would naturally expect many (if not most) of the problems occurring in these areas to be complete for the classes Sigmap2 or Sigmap3 from the polynomial hierarchy, almost no hardness results in this regime are currently known. However, such complexity insights are important, since they imply that no polynomial-sized integer program for these min-max problems exist, and hence conventional IP-based approaches fail. We address this lack of knowledge by introducing over 70 new Sigmap2-complete and Sigmap3-complete problems. The majority of all earlier publications on Sigmap2- and Sigmap3-completeness in said areas are special cases of our meta-theorem. Precisely, we introduce a large list of problems for which the meta-theorem is applicable (including clique, vertex cover, knapsack, TSP, facility location and many more). We show that for every single of these problems, the corresponding min-max (i.e. interdiction/regret) variant is Sigmap2- and the min-max-min (i.e. two-stage) variant is Sigmap3-complete.