Gap Amplification for Reconfiguration Problems
Author:
Open Access
- 6 February 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (2) , 1-38
Abstract
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 \(\mathbf{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\cdots 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 article, we demonstrate gap amplification for reconfiguration problems. Specifically, we establish explicit \(\mathbf{PSPACE}\) -hardness of approximation factors for three reconfiguration problems, assuming only RIH. Our main result is that under RIH, Maxmin 2-CSP Reconfiguration is \(\mathbf{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-\varepsilon\) gap to the 1 vs. \(1-0.0058\) gap for any small positive real \(\varepsilon\) . As an application of the main result, we further show that Minmax Set Cover Reconfiguration and Minmax Dominating Set Reconfiguration are \(\mathbf{PSPACE}\) -hard to approximate within a factor of 1.0029 under RIH.
Keywords
This publication has 59 references indexed in Scilit:
- Explicit Expanders of Every Degree and SizeCombinatorica, 2021
- Decremental Optimization of Dominating Sets Under the Reconfiguration Framework2020
- Approximating Shortest Connected Graph Transformation for TreesLecture Notes in Computer Science, 2020
- Shortest Reconfiguration of MatchingsLecture Notes in Computer Science, 2019
- Complexity of Token Swapping and Its VariantsAlgorithmica, 2017
- Approximability of the subset sum reconfiguration problemJournal of Combinatorial Optimization, 2012
- On the solution‐space geometry of random constraint satisfaction problemsRandom Structures & Algorithms, 2011
- Finding paths between 3-coloringsJournal of Graph Theory, 2010
- Gap Amplification in PCPs Using Lazy Random WalksLecture Notes in Computer Science, 2006
- Clique is hard to approximate within n1−εActa Mathematica, 1999