Gap Amplification for Reconfiguration Problems

Combinatorial reconfiguration is an emerging field of theoretical computer science that studies the reachability between a pair of feasible solutions for a particular combinatorial problem. We study the hardness of accomplishing “approximate” reconfigurability, which affords to relax the feasibility of solutions. For example, in Minmax Set Cover Reconfiguration, given a pair of covers Cs and Ct for a set system F, we aim to transform Cs into Ct by repeatedly adding or removing a single set of F so as to minimize the maximum size of covers during transformation. The recent study by Ohsaka (STACS 2023) [Ohs23b] gives evidence that a host of reconfiguration problems are PSPACE-hard to approximate assuming the Reconfiguration Inapproximability Hypothesis (RIH), which postulates that a gap version of Maxmin CSP Reconfiguration is PSPACE-hard. 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 2-approximation as per Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara, and Uno (Theor. Comput. Sci., 2011) [IDHPSU+11].