Asymptotic Inapproximability of Reconfiguration Problems: Maxmin $k$-Cut and Maxmin E$k$-SAT
<|reference_start|>Asymptotic Inapproximability of Reconfiguration Problems: Maxmin $k$-Cut and Maxmin E$k$-SAT: We study the hardness of approximating two reconfiguration problems. One problem is Maxmin $k$-Cut Reconfiguration, which is a reconfiguration analogue of Max $k$-Cut. The other is Maxmin E$k$-SAT Reconfiguration, which is a reconfiguration analogue of Max E$k$-SAT. The Probabilistically Checkable Reconfiguration Proof theorem due to Hirahara and Ohsaka (STOC 2024) and Karthik C. S. and Manurangsi (2023) implies that Maxmin 4-Cut Reconfiguration and Maxmin E3-SAT Reconfiguration are PSPACE-hard to approximate within a constant factor. However, the asymptotic behavior of approximability for these problems with respect to $k$ is not well understood.   In this paper, we present the following hardness-of-approximation results and approximation algorithms for Maxmin $k$-Cut Reconfiguration and Maxmin E$k$-SAT Reconfiguration:   $\bullet$ For every $k \geq 2$, Maxmin $k$-Cut Reconfiguration is PSPACE-hard to approximate within a factor of $1 - \Omega\left(\frac{1}{k}\right)$, whereas it can be approximated within a factor of $1-\frac{2}{k}$. Our lower and upper bounds demonstrate that Maxmin $k$-Cut Reconfiguration exhibits the asymptotically same approximability as Max $k$-Cut.   $\bullet$ For every $k \geq 3$, Maxmin E$k$-SAT Reconfiguration is PSPACE-hard (resp. NP-hard) to approximate within a factor of $1-\Omega\left(\frac{1}{9^{\sqrt{k}}}\right)$ (resp. $1-\frac{1}{8k}$). On the other hand, it admits a deterministic $\left(1-\frac{2.5}{k}\right)$-factor approximation algorithm, implying that Maxmin E$k$-SAT Reconfiguration displays an asymptotically approximation threshold different from Max E$k$-SAT.<|reference_end|>
@article{hirahara2024asymptotic,
    title={Asymptotic Inapproximability of Reconfiguration Problems: Maxmin $k$-Cut
  and Maxmin E$k$-SAT},
    author={Shuichi Hirahara, Naoto Ohsaka},
    journal={arXiv preprint arXiv:2410.03416},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.03416},
    primaryClass={cs.CC cs.DM cs.DS}
}