Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Computational Complexity of the Game of Set and its Theoretical
  Applications   The game of SET is a popular card game in which the objective 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 computational 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 Perfect
Multi-Dimensional Matching, a result which may be of independent 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 possible 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.

0
The categories of this paper are: hep-ph
22
The categories of this paper are: chao-dyn
8
The categories of this paper are: hep-ex
12
The categories of this paper are: nucl-th
28
The categories of this paper are: alg-geom
29
The categories of this paper are: funct-an
36
The categories of this paper are: cmp-lg
24
The categories of this paper are: dg-ga
20
The categories of this paper are: acc-phys
25
The categories of this paper are: patt-sol
34
The categories of this paper are: chem-ph
35
The categories of this paper are: mtrl-th
7
The categories of this paper are: hep-th
13
The categories of this paper are: quant-ph
30
The categories of this paper are: q-alg
10
The categories of this paper are: q-bio