Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:The computational complexity of two card games with theoretical applications
Speaker:Valia Mitsou
coming from:Hokkaido University (Sapporo, Japan)
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 20 November 2014
Duration:30 Minutes
Building:E1 4
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.

Name(s):Holger Dell
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Holger Dell, 11/18/2014 02:37 PM
  • Holger Dell, 11/17/2014 02:10 PM
  • Holger Dell, 11/17/2014 02:10 PM -- Created document.