Center for Algorithms and Theory of Computation

CS 269S, Winter 2019: Theory Seminar
Bren Hall, Room 1423, 1pm


Februaru 22, 2019:

Two-Dots is NP-complete

Speaker: Martha Osegueda

Two-dots is a mobile game where same-coloured dots are linked, to form a move after which they disappear. The objective of the game is to hit certain required number of dots of different colours. The paper proves hardness for the constant goals and for cases without special moves, and completeness for the general case.

Based on a paper by Neeldhara Misra.