Gap Amplification for Reconfiguration Problems

Abstract

In this paper, we demonstrate gap amplification for reconfiguration problems. In particular, we prove an explicit factor of PSPACE-hardness of approximation for three popular reconfiguration problems only assuming the Reconfiguration Inapproximability Hypothesis (RIH) due to Ohsaka (STACS 2023). Our main result is that under RIH, Maxmin 2-CSP Reconfiguration is PSPACE-hard to approximate within a factor of $0.9942$. Moreover, the same result holds even if the constraint graph is restricted to $(d,\lambda )$-expander for arbitrarily small $\frac{\lambda }{d}$. The crux of its proof is an alteration of the gap amplification technique due to Dinur (J. ACM, 2007), which amplifies the $1$ vs. $1-\epsilon$ gap for arbitrarily small $\epsilon \in (0,1)$ up to the $1$ vs. $1-0.0058$ gap. As an application of the main result, we demonstrate that Minmax Set Cover Reconfiguration and Minmax Dominating Set Reconfiguratio} are PSPACE-hard to approximate within a factor of $1.0029$ under RIH. Our proof is based on a gap-preserving reduction from Label Cover to Set Cover due to Lund and Yannakakis (J. ACM, 1994). Unlike Lund--Yannakakis' reduction, the expander mixing lemma is essential to use. We highlight that all results hold unconditionally as long as "PSPACE-hard" is replaced by "NP-hard," and are the first explicit inapproximability results for reconfiguration problems without resorting to the parallel repetition theorem. We finally complement the main result by showing that it is NP-hard to approximate Maxmin 2-CSP Reconfiguration within a factor better than $\frac{3}{4}$.

arXiv comment45 pages. A preliminary version of this paper appeared in Proc. 35th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA 2024)

References in corpus (7)

• Clustering of solutions in the random satisfiability problem
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Reconfiguration Problems on Submodular Functions
• Gap Preserving Reductions Between Reconfiguration Problems
• On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
• Alphabet Reduction for Reconfiguration Problems
• Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration

Cited by in corpus (1)

• On Approximate Reconfigurability of Label Cover