The computational complexity of two card games with theoretical applications

Valia Mitsou (Hokkaido University, Japan)

When: June 22, 2pm

Where: room C417


The main theme of this talk is card games that can be naturally reformulated as well-known graph-theoretic problems. In particular, we will focus on two different games: the game of SET, and the game of UNO. The objective of the former is to form sets of cards that match in a certain sense, while in the latter players need to discard their cards following a matching rule (for more details regarding the rules of the two games please visit the following websites: official website of SET, wikihow: how to play UNO).

We will describe connections of the two games with a number of different problems such as Multidimensional Matching, Set Packing, Edge Dominating Set, and Hamiltonian Path. These connections will help us show algorithmic as well as hardness results for variations of both games in the classical and the parameterized sense. The connections described are two-fold as our results will, in several cases, imply progress for the state of the art of the corresponding graph-theoretic problems.

This talk will include results from two different publications: “The computational complexity of the game of SET”, joint with Michael Lampis, LATIN 2014, and “Parameterized Edge Hamiltonicity”, joint with Michael Lampis, Kazuhisa Makino, and Yushi UNO, WG 2014.