Gap Amplification for Reconfiguration Problems

Combinatorial reconfiguration is a brand-new field aimed at investigating the connectivity of the solution space of a combinatorial problem. We study the hardness of achieving “approximate” reconfigurability, which allows to relax the feasibility of intermediate solutions. For example, in the Minmax Set Cover Reconfiguration problem, given a set family and a pair of its covers, we are asked to transform one cover into the other by repeatedly adding or removing a single set from the family. The objective is to minimize the maximum size of covers encountered during the transformation. The recent study by Ohsaka (STACS 2023) showed that several reconfiguration problems are PSPACE-hard to approximate assuming the Reconfiguration Inapproximability Hypothesis (RIH) . One limitation of this approach is that inapproximability factors are not explicitly shown, so that even a \(1.00⋯ 001\) -approximation algorithm for Minmax Set Cover Reconfiguration may not be ruled out, whereas it admits a \(2\) -factor approximation algorithm due to Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara, and Uno (TCS 2011). In this paper, we demonstrate gap amplification for reconfiguration problems. Specifically, we establish explicit PSPACE-hardness of approximation factors for three reconfiguration problems, assuming only RIH. Our main result is that under RIH, Maxmin 2-CSP Reconfiguration is PSPACE-hard to approximate within a factor of \(0.9942\) . The crux of its proof is an alteration of the gap amplification technique due to Dinur (JACM 2007), which boosts the \(1\) vs. \(1-ε\) gap to the \(1\) vs. \(1-0.0058\) gap for any small positive real \(ε\) . As an application of the main result, we further show that Minmax Set Cover Reconfiguration and Minmax Dominating Set Reconfiguration are PSPACE-hard to approximate within a factor of \(1.0029\) under RIH.