In the problem NODE KAYLES two opposing players take turns playing on an undirected graph. In each turn, a player selects a vertex $u$ and removes $u$ and all its neighbors from the graph. The first player who is unable to select a vertex loses. In other words, the two players take turns selecting vertices under the constraint that the set of all selected vertices must be independent.

NODE KAYLES was shown to be PSPACE-complete by Schaefer in the late '70s. (See "On the complexity of some two-person perfect-information games", Thomas J. Schaefer, JCSS 1978). In the same paper, the edge version of the game, called there ARC KAYLES, is mentioned as an open problem. In ARC KAYLES, players take turns selecting edges (rather than vertices) under the constraint that the set of edges selected is independent (i.e. a matching).

My question is if the complexity of ARC KAYLES is still open. I have seen a few more recent papers on NODE KAYLES (e.g. "Kayles and Nimbers", by Bodlaender and Kratsch) but I haven't been able to find a reference on any follow-up work regarding ARC KAYLES. Is it by now known that ARC KAYLES is PSPACE-complete?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.