3 papers
cs.DS2025
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…
cs.DS2025
Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes
Toranosuke Kokai, Akira Suzuki, Takahiro Suzuki +2
In the context of algorithm theory, various studies have been conducted on spanning trees with desirable properties. In this paper, we consider the \textsc{Minimum Cover Spanning T…
cs.DS2025
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…