8 papers
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…
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…
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…
Communication Complexity is NP-hard
Shuichi Hirahara, Rahul Ilango, Bruno Loff
In the paper where he first defined Communication Complexity, Yao asks: \emph{Is computing (the 2-way communication complexity of a given function ) NP-complete?} The pr…
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…