11 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…
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…
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…
Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules
Tatsuhiro Suga, Akira Suzuki, Yuma Tamura +1
In a reconfiguration problem, we are given two feasible solutions of a combinatorial problem and our goal is to determine whether it is possible to reconfigure one into the other,…
Finding Induced Subgraphs from Graphs with Small Mim-Width
Yota Otachi, Akira Suzuki, Yuma Tamura
In the last decade, algorithmic frameworks based on a structural graph parameter called mim-width have been developed to solve generally NP-hard problems. However, it is known that…
On the complexity of list -packing for sparse graph classes
Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi +5
The problem of packing as many subgraphs isomorphic to as possible in a graph for a class of graphs is well studied in the literature. Both vertex-d…