Answers are grounded in this paper and cite their sources.
Combinatorial reconfiguration is a brand-new field studying algorithmic problems relating to the structure of the solution space. In this paper, we study the hardness of approximate versions of reconfiguration problems. For example, in the Maxmin SAT Reconfiguration problem, we are given a satisfiable Boolean formula and a pair of its satisfying assignments. The objective is to transform one satisfying assignment into the other by repeatedly flipping the value of a single variable, while maximizing the minimum fraction of satisfied clauses throughout the transformation. We prove a series of gap-preserving reductions to give evidence that several reconfiguration problems are PSPACE -hard to approximate. Our starting point is a new working hypothesis called the Reconfiguration Inapproximability Hypothesis (RIH), which asserts that a gap version of Maxmin CSP Reconfiguration is PSPACE -hard. Our main result is PSPACE -hardness of approximating Maxmin 3-SAT Reconfiguration of bounded occurrence under RIH. The crux of its proof is a gap-preserving reduction from Maxmin 2-CSP Reconfiguration to itself of bounded degree. As an application of the main result, we demonstrate that under RIH, approximate versions of reconfiguration problems are PSPACE -hard to approximate, including Nondeterministic Constraint Logic , Independent Set Reconfiguration , Clique Reconfiguration , Vertex Cover Reconfiguration , and 2-SAT Reconfiguration . We highlight that RIH has recently been proven by Hirahara and Ohsaka (STOC 2024) and Karthik C.S. and Manurangsi (2023).
No takes yet. Share an insight, caveat, or question.
Naoto Ohsaka (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: