4 papers
Parameterized Complexity of Odd Domination and its Generalization
Toranosuke Kokai, Rin Saito, Tatsuhiro Suga +2
In the \textsc{Odd Domination} problem, given a graph and a positive integer , the task is to determine whether there exists a vertex subset of such that the closed…
On (In)approximability of MaxMin Independent Set Reconfiguration
Hung P. Hoang, Naoto Ohsaka, Rin Saito +1
In the Independent Set Reconfiguration problem under the Token Addition/Removal rule, given a graph and two independent sets and of , we want to transform into $…
Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
Rin Saito, Anouk Sommer, Tatsuhiro Suga +2
In the solution discovery problem for a search problem on graphs, we are given an initial placement of tokens on the vertices of a graph and asked whether this placement can be…
Coloring Reconfiguration under Color Swapping
Janosch Fuchs, Rin Saito, Tatsuhiro Suga +2
In the \textsc{Coloring Reconfiguration} problem, we are given two proper -colorings of a graph and asked to decide whether one can be transformed into the other by repeatedly a…