6 papers
PSPACE-Completeness of Multi-Agent Path Finding for Large Agents
Maichi Zhang, Naoyuki Kamiyama, Kanae Yoshiwatari
Multi-Agent Path Finding for Large Agents (LA-MAPF) is a geometric variant of MAPF in which agents are modeled as disks and conflicts are determined by physical overlap in the unde…
Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
Kyle Burke, Caroline Cashman, Alfie Davies +2
We show that Misère Partizan Arc Kayles is PSPACE-complete on planar graphs via a reduction from Bounded Two-Player Constraint Logic. Furthermore, we show how to embed our gadgets…
Digraph Yama Nim
Hiyu Inoue, Shun-ichi Kimura, Hikaru Manabe +3
{\sc Yama Nim} is a variant of two piles {\sc Nim}. In this ruleset, the player chosses one of the piles and removes at least two tokens from the pile. In the same move, the player…
Parameterized Vertex Integrity Revisited
Tesshu Hanaka, Michael Lampis, Manolis Vasilakis +1
Vertex integrity is a graph parameter that measures the connectivity of a graph. Informally, its meaning is that a graph has small vertex integrity if it has a small separator whos…
Turning Tiles is PSPACE-complete
Kanae Yoshiwatari, Hironori Kiya, Koki Suetsugu +2
In combinatorial game theory, the winning player for a position in normal play is analyzed and characterized via algebraic operations. Such analyses define a value for each positio…
Winner Determination Algorithms for Graph Games with Matching Structures
Tesshu Hanaka, Hironori Kiya, Hirotaka Ono +1
Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They are interpreted as edge-selecting-type games on graphs, and the selected edges during a game form a mat…