logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

Gap Amplification for Reconfiguration Problems

delete2026-04-01
delete0
PRE
AI
O
Ohsaka, Naoto *
DOI：10.1145/3779053delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
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 & centerdot; & centerdot; & centerdot; 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 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 F. 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.
Keywords:
Reconfiguration Problems
Hardness of Approximation
Probabilistic Proof Systems
PSPACE-hardness

Journal

A
ACM Transactions on Algorithms
IF:
1.4
Papers:
43
Citations:
1.1K

Organization

No organization information available