3 papers
cs.CC2026
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…
cs.CC2025
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…
math.CO2025
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…