The Computational Complexity of the Game of Set and its Theoretical Applications

Abstract. The game of SET is a popular card game in which the ob-jective is to form Sets using cards from a special deck. In this paper we study single- and multi-round variations of this game from the compu-tational complexity point of view and establish interesting connections with other classical computational problems. Specifically, we first show that a natural generalization of the problem of finding a single Set, parameterized by the size of the sought Set is W-hard; our reduction applies also to a natural parameterization of Per-fect Multi-Dimensional Matching, a result which may be of inde-pendent interest. Second, we observe that a version of the game where one seeks to find the largest possible number of disjoint Sets from a given set of cards is a special case of 3-Set Packing; we establish that this restriction remains NP-complete. Similarly, the version where one seeks to find the smallest number of disjoint Sets that overlap all possi-ble Sets is shown to be NP-complete, through a close connection to the Independent Edge Dominating Set problem. Finally, we study a 2-player version of the game, for which we show a close connection to Arc Kayles, as well as fixed-parameter tractability when parameterized by the number of rounds played.