dorsal/arxiv
View SchemaComputational Complexity of Swish
| Authors | Takashi Horiyama, Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Akira Suzuki, Ryuhei Uehara, Yutaro Yamaguchi |
|---|---|
| Categories | |
| ArXiv ID | 2601.09289vv1 |
| URL | https://arxiv.org/abs/2601.09289 |
| License | http://creativecommons.org/licenses/by/4.0/ |
Abstract
Swish is a card game in which players are given cards having symbols (hoops and balls), and find a valid superposition of cards, called a "swish." Dailly, Lafourcade, and Marcadet (FUN 2024) studied a generalized version of Swish and showed that the problem is solvable in polynomial time with one symbol per card, while it is NP-complete with three or more symbols per card. In this paper, we resolve the previously open case of two symbols per card, which corresponds to the original game. We show that Swish is NP-complete for this case. Specifically, we prove the NP-hardness when the allowed transformations of cards are restricted to a single (horizontal or vertical) flip or 180-degree rotation, and extend the results to the original setting allowing all three transformations. In contrast, when neither transformation is allowed, we present a polynomial-time algorithm. Combining known and our results, we establish a complete characterization of the computational complexity of Swish with respect to both the number of symbols per card and the allowed transformations.
{
"annotation_id": "d60eeeb6-eab8-478a-81fc-03ec6da94c4f",
"date_created": "2026-02-17T05:53:20.455000Z",
"date_modified": "2026-02-17T05:53:20.455000Z",
"file_hash": "ad7d0518bbdbfba62e29db2da9cba5ed0b7eb85f9b6f1c68dd0187e98f087080",
"private": false,
"record": {
"abstract": "Swish is a card game in which players are given cards having symbols (hoops and balls), and find a valid superposition of cards, called a \"swish.\" Dailly, Lafourcade, and Marcadet (FUN 2024) studied a generalized version of Swish and showed that the problem is solvable in polynomial time with one symbol per card, while it is NP-complete with three or more symbols per card. In this paper, we resolve the previously open case of two symbols per card, which corresponds to the original game. We show that Swish is NP-complete for this case. Specifically, we prove the NP-hardness when the allowed transformations of cards are restricted to a single (horizontal or vertical) flip or 180-degree rotation, and extend the results to the original setting allowing all three transformations. In contrast, when neither transformation is allowed, we present a polynomial-time algorithm. Combining known and our results, we establish a complete characterization of the computational complexity of Swish with respect to both the number of symbols per card and the allowed transformations.",
"arxiv_id": "2601.09289",
"authors": [
"Takashi Horiyama",
"Takehiro Ito",
"Jun Kawahara",
"Shin-ichi Minato",
"Akira Suzuki",
"Ryuhei Uehara",
"Yutaro Yamaguchi"
],
"categories": [
"cs.DS",
"cs.CC",
"math.CO"
],
"license": "http://creativecommons.org/licenses/by/4.0/",
"title": "Computational Complexity of Swish",
"url": "https://arxiv.org/abs/2601.09289",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "2d9a3e0a-1604-4264-ad11-4dbb2376e3a3",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}