OLYMPIADS IN INFORMATICS, 2016, Vol. 10, pp. 87 - 98
© IOI, Vilnius University
Understanding Unsolvable Problem
Jonathan Irvin GUNAWAN
School of Computing, National University of Singapore
Computing 1, 13 Computing Drive, Singapore 117417
In recent IOIs, there are several problems that seem unsolvable, until we realise that there is a special case to the problem that makes it tractable. In IOI 2014, the problem ‘Friend’ appears to be a standard NP-hard Maximum Independent Set problem. However, the graph is generated in a very special way, hence there is a way to solve the problem in polynomial time. There were several contestants who didn’t identify the special case in this problem, and hence were stuck at the problem. In this paper, we will study a well-known technique called reduction to show that a problem we are currently tackling is intractable. In addition, we introduce techniques to identify special cases such that contestants will be prepared to tackle these problems.
special case, unsolvable, NP-hard.
To preview full article text in PDF format click here
You could obtain free Acrobat Reader from Adobe
Copyright © International Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2016