14 citations · 59 across the 21 of their papers we have counts for
4 papers · 1 filter
Asymptotically Optimal Inapproximability of Maxmin -Cut Reconfiguration
Shuichi Hirahara, Naoto Ohsaka
-Coloring Reconfiguration is one of the most well-studied reconfiguration problems, which asks to transform a given proper -coloring of a graph to another by repeatedly recol…
Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
Shuichi Hirahara, Naoto Ohsaka
In the Minmax Set Cover Reconfiguration problem, given a set system over a universe and its two covers and of…
Alphabet Reduction for Reconfiguration Problems
Naoto Ohsaka
We present a reconfiguration analogue of alphabet reduction à la Dinur (J. ACM, 2007) and its applications. Given a binary constraint graph and its two satisfying assignments $…
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
Shuichi Hirahara, Naoto Ohsaka
Motivated by the inapproximability of reconfiguration problems, we present a new PCP-type characterization of PSPACE, which we call a probabilistically checkable reconfiguration pr…