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…