5 citations · 24 across the 16 of their papers we have counts for
6 papers · 1 filter
Complexity of Jelly-No and Hanano games with various constraints
Owen Crabtree, Valia Mitsou
This work shows new results on the complexity of games Jelly-No and Hanano with various constraints on the size of the board and number of colours. Hanano and Jelly-No are one-play…
Fine-grained Meta-Theorems for Vertex Integrity
Michael Lampis, Valia Mitsou
Vertex Integrity is a graph measure which sits squarely between two more well-studied notions, namely vertex cover and tree-depth, and that has recently gained attention as a struc…
Complexity and Approximability of Parameterized MAX-CSPs
Holger Dell, Eun Jung Kim, Michael Lampis +2
We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constr…
The Computational Complexity of the Game of Set and its Theoretical Applications
Michael Lampis, Valia Mitsou
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 gam…
Scrabble is PSPACE-Complete
Michael Lampis, Valia Mitsou, Karolina Sołtys
In this paper we study the computational complexity of the game of Scrabble. We prove the PSPACE-completeness of a derandomized model of the game, answering an open question of Eri…
Vertex Cover Problem Parameterized Above and Below Tight Bounds
Gregory Gutin, Eun Jung Kim, Michael Lampis +1
We study the well-known Vertex Cover problem parameterized above and below tight bounds. We show that two of the parameterizations (both were suggested by Mahajan, Raman and Sikdar…