The Computational Complexity of Sprouts

Skip to first unread message

Josh Jordan

Feb 13, 2011, 2:44:32 AM2/13/11
to sprouts-theory
In [1] it is shown that the problem of determining whether play from
an arbitrary sprouts position can continue for more than k moves is NP-
complete. The paper also shows that the analagous problem of
determining whether, when starting from an arbitrary sprouts position,
the game can end in fewer than k moves is also NP-complete. The proofs
are clever but simple, and proceed by reduction from Planar Cubic
Graph Maximum Independent Set, the NP-completeness of which was shown
in [2].

Since winning a game of sprouts amounts to controlling the number of
moves for which the game lasts, it's natural to ask whether a
particular sprouts position can last for more (or less) than k moves.
For example, one might ask whether the position consisting of two
initial spots can last for more than k=5 moves. Here, the answer is
clearly no. However, the results of [1] tell us that this is a hard
problem in general; computer scientists will be flabbergasted if an
efficient algorithm is ever found to answer this question for
arbitrary sprouts positions and arbitrary values of k.

[1] Baird & Schweitzer. Complexity of the Game of Sprouts. FCS'10 -
6th International Conference on Foundations of Computer Science
[2] Garey & Johnson. The Rectilinear Steiner Tree Problem is NP-
Complete. Siam J. Applied Math 6 (1977) 826-834.
Reply all
Reply to author
0 new messages