The field of combinatorial reconfiguration studies search problems with a focus on transforming one feasible solution into another.

Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts that there is some $\varepsilon>0$ such that given as input a $k$-CSP instance (for some constant $k$) over some constant sized alphabet, and two satisfying assignments $\psi_s$ and $\psi_t$, it is PSPACE-hard to find a sequence of assignments starting from $\psi_s$ and ending at $\psi_t$ such that every assignment in the sequence satisfies at least $(1-\varepsilon)$ fraction of the constraints and also that every assignment in the sequence is obtained by changing its immediately preceding assignment (in the sequence) on exactly one variable. Assuming RIH, many important reconfiguration problems have been shown to be PSPACE-hard to approximate by Ohsaka [STACS'23; SODA'24].

In this paper, we prove RIH, thus establishing the first (constant factor) PSPACE-hardness of approximation results for many reconfiguration problems, resolving an open question posed by Ito et al. [TCS'11]. Our proof uses known constructions of Probabilistically Checkable Proofs of Proximity (in a black-box manner) to create the gap. Independent to our work, Hirahara and Ohsaka [STOC'24] have also proved RIH.

We also prove that the aforementioned $k$-CSP Reconfiguration problem is NP-hard to approximate to within a factor of $1/2 + \varepsilon$ (for any $\varepsilon>0$) when $k=2$. We complement this with a $(1/2 - \varepsilon)$-approximation polynomial time algorithm, which improves upon a $(1/4 - \varepsilon)$-approximation algorithm of Ohsaka [2023] (again for any $\varepsilon>0$).

Finally, we show that Set Cover Reconfiguration is NP-hard to approximate to within a factor of $2 - \varepsilon$ for any constant $\varepsilon > 0$, which matches the simple linear-time 2-approximation algorithm by Ito et al. [TCS'11].

Added a remark to independent work of Hirahara and Ohsaka.

The field of combinatorial reconfiguration studies search problems with a focus on transforming one feasible solution into another.

Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts that there is some $\varepsilon>0$ such that given as input a $k$-CSP instance (for some constant $k$) over some constant sized alphabet, and two satisfying assignments $\psi_s$ and $\psi_t$, it is PSPACE-hard to find a sequence of assignments starting from $\psi_s$ and ending at $\psi_t$ such that every assignment in the sequence satisfies at least $(1-\varepsilon)$ fraction of the constraints and also that every assignment in the sequence is obtained by changing its immediately preceding assignment (in the sequence) on exactly one variable. Assuming RIH, many important reconfiguration problems have been shown to be PSPACE-hard to approximate by Ohsaka [STACS'23; SODA'24].

In this paper, we prove RIH, thus establishing the first (constant factor) PSPACE-hardness of approximation results for many reconfiguration problems, resolving an open question posed by Ito et al. [TCS'11]. Our proof uses known constructions of Probabilistically Checkable Proofs of Proximity (in a black-box manner) to create the gap.

We also prove that the aforementioned $k$-CSP Reconfiguration problem is NP-hard to approximate to within a factor of $1/2 + \varepsilon$ (for any $\varepsilon>0$) when $k=2$. We complement this with a $(1/2 - \varepsilon)$-approximation polynomial time algorithm, which improves upon a $(1/4 - \varepsilon)$-approximation algorithm of Ohsaka [2023] (again for any $\varepsilon>0$).

Finally, we show that Set Cover Reconfiguration is NP-hard to approximate to within a factor of $2 - \varepsilon$ for any constant $\varepsilon > 0$, which matches the simple linear-time 2-approximation algorithm by Ito et al. [TCS'11].