Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
Optimal PSPACE-hardness of Approximating -CSP Reconfiguration
Shuichi Hirahara, Naoto Ohsaka
In the Maxmin -CSP Reconfiguration problem, given a satisfiable -CSP instance and a pair of its satisfying assignments, we are asked to transform one assignment into the othe…
cs.CC2025
Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules
Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga +3
In reconfiguration problems, we are given two feasible solutions to a graph problem and asked whether one can be transformed into the other via a sequence of feasible intermediate…
cs.CC2025
Asymptotically Optimal Inapproximability of E-SAT Reconfiguration
Shuichi Hirahara, Naoto Ohsaka
In the Maxmin E-SAT Reconfiguration problem, we are given a satisfiable -CNF formula where each clause contains exactly literals, along with a pair of its satisfying…