It's Hard to PArcK

Kyle Burke, Jeffrey Leman, Craig Tennenhouse

We show that Partizan Arc Kayles (PArcK), a generalization of Domineering to graphs, is PSPACE-complete via a reduction from Positive CNF and with recently-discovered techniques fo…