10 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…
Distance-Constrained Unlabeled Multi-Agent Pathfinding
Takahiro Suzuki, Yuma Tamura, Keisuke Okumura
We study a graph pathfinding problem Distance- Independent Unlabeled Multi-Agent Pathfinding, finding a set of collision-free paths between two sets where agents must stay at pa…
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 $…
Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
Jean Cardinal, Kevin Mann, Akira Suzuki +3
We initiate the study of the shortest reconfiguration problem for independent sets under the adjacency relation derived from the independent set polytope. Given a graph and two ind…
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…
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…