Subset Search Problems (in short SSP problems) are a class of combinatorial problems that posses a universe $U$ as their structural ground set and all solutions $S$ are encodable as a subset of this universe $U$, i.e. $S \in 2^U$. This class of problems was introduced by Grüne and Wulf in [GW2024] as an abstraction for linear optimization problems. With the help of this abstraction, one is able to show for several classes of problems in robust and bilevel optimization that if the nominal problem, e.g. VERTEX COVER, is NP-complete, then the corresponding min-max version, e.g. INTERDICTION VERTEX COVER or INTERVAL MIN-MAX REGRET VERTEX COVER, sits on a higher level in the polynomial hierarchy, precisely they are $\Sigma^p_2$-complete.
Formally, SSP problems are defined as follows.
Definition (Subset Search Problem (SSP), from [GW2024]) A subset Search problem $\Pi$ is a tuple $(\mathcal{I}, \mathcal {U},\mathcal{S})$, such that
- $\mathcal{I} \subseteq \{0,1\}^*$ is a language. We call $\mathcal{I}$ the set of instances.
- To each instance $I \in \mathcal{I}$, there is some set $\mathcal{U}(I)$ which we call the universe associated to the instance $I$.
- To each instance $I \in \mathcal{I}$, there is some (potentially empty) set $\mathcal{S}(I)\subseteq 2^{\mathcal{U}(I)}$ which we call the solution set associated to the instance $I$.
SSP Reductions
An SSP reduction is a transformation from one problem $\Pi$ into another problem $\Pi'$ that is a typical (polynomial time) reduction but additionally includes an injective mapping $f$ that embeds the solution elements of $\Pi$ into the solutions elements of $\Pi'$. This embedding allows $\Pi$ to be viewed as a 'subinstance' of $\Pi'$ while preserving the topology of solutions within the subset induced by the image of $f$. More precisely, we interpret $W$ as the subinstance of $\Pi$ within the instance of $\Pi'$ and we require the following conditions to be met:
- For every solution $S'$ of $\Pi'$, the set
- For every solution $S$ of $\Pi$, the set $f(S)$ is a partial solution of $\Pi'$ and can be extended to a full solution using elements that are not in $W$.
Formally, SSP reductions are defined as follows
Definition (SSP Reduction, from [GW2024]) Let $\Pi = (\mathcal{I},\mathcal{U},\mathcal{S})$ and $\Pi' = (\mathcal{I}',\mathcal{U}',\mathcal{S}')$ be two SSP problems. We say that there is an SSP reduction from $\Pi$ to $\Pi'$, and write $\Pi \leq_{SSP} \Pi'$, if
- There exists a function $g : \mathcal{I} \to \mathcal{I}'$ computable in polynomial time in the input size $|I|$, such that $I$ is a Yes-instance iff $g(I)$ is a Yes-instance (i.e. $\mathcal{S}(I) \neq \emptyset$ iff $\mathcal{S}'(g(I)) \neq \emptyset$).
- There exist functions $(f_I)_{I \in \mathcal{I}}$ computable in polynomial time in $|I|$ such that for all instances $I \in \mathcal{I}$, we have that $f_I : \mathcal{U}(I) \to \mathcal{U}'(g(I))$ is an injective function mapping from the universe of the instance $I$ to the universe of the instance $g(I)$ such that $$ \set{f_I(S) : S \in \mathcal{S}(I) } = \set{S' \cap f_I(\mathcal{U}(I)) : S' \in \mathcal{S}'(g(I))}. $$
SSP reductions are transitive, and it turns out that the reduction of the Cook-Levin theorem showing that SATISFIABILITY is NP-complete is also an SSP reduction. Accordingly, Grüne and Wulf define the class SSP-NP of to consist of all SSP problems that are in NP as well as SSP-NP-completeness as completeness under SSP reductions.
Applications
The main application of the SSP framework is to derive completeness results of robust and bilevel optimization problems within the polynomial hierarchy. More precisely, the following theorems apply under the above notion of SSP problems and reductions.
Theorem For all SSP-NP-complete problems $\Pi$, the interdiction variant INTERDICTION-$\Pi$ is $\Sigma^p_2$-complete.
For the following theorems, it is necessary to define linear optimization problems (LOP) as basic concept. An LOP problem describes combinatorial problems with linear optimization function and is defined as a 5-tuple $(\mathcal{I}, \mathcal{U}, \mathcal{F}, d, t)$. Here, $\mathcal{I} \subseteq \{0,1\}^*$ is the set of input instances of the problem encoded as words in binary. Associated to each input instance $I \in \mathcal{I}$, we assume that there is a universe $\mathcal{U}(I)$, a linear cost function $d^{(I)} : \mathcal{U}(I) \to \mathbb{Z}$ over the universe, the feasible sets $\mathcal{F}(I) \subseteq 2^{\mathcal{U}(I)}$ containing all feasible subsets of the universe, and a threshold $t^{(I)}$. For LOP problems, it is always possible to derive a corresponding SSP problem by setting $\mathcal{S}(I) := \set{F \in \mathcal{F}(I) : d^{(I)}(F) \leq t^{(I)}}$ and inheriting the instances $\mathcal{I}$ and the universes $\mathcal{U}$.
Theorem For all LOP problems $\Pi$ with the property that the SSP problem derived from them is SSP-NP-complete, the interval min-max regret variant INTERVAL MIN-MAX REGRET-$\Pi$ is $\Sigma^p_2$-complete.
Theorem For all LOP problems $\Pi$ with the property that the SSP problem derived from them is SSP-NP-complete, the two-stage adjustable variant TWO-STAGE ADJUSTABLE-$\Pi$ is $\Sigma^p_3$-complete.