Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-007 | 15th February 2024 20:11

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results

RSS-Feed




Revision #1
Authors: Karthik C. S., Pasin Manurangsi
Accepted on: 15th February 2024 20:11
Downloads: 4
Keywords: 


Abstract:

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].



Changes to previous version:

Added a remark to independent work of Hirahara and Ohsaka.


Paper:

TR24-007 | 25th December 2023 00:36

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results





TR24-007
Authors: Karthik C. S., Pasin Manurangsi
Publication: 14th January 2024 11:12
Downloads: 72
Keywords: 


Abstract:

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].



ISSN 1433-8092 | Imprint