Finding Hidden Independent Sets in Interval Graphs. Therese Biedl, Broňa Brejova, Erik D. Demaine, Angele M. Hamel, A. López-Ortiz and Tomas Vinař. In Proceedings of 9th Annual International Computing and Combinatorics Conference, (COCOON), Lecture Notes in Computer Science 2697, Springer-Verlag, pp. 182-191, 2003. [Postscript file]

Abstract.
Consider a game in a given set of intervals (and their implied interval graph G) in which the adversary chooses an independent set X in G. The goal is to discover this hidden independent set X by making the fewest queries of the form ``Is point p covered by an interval in X?'' Our interest in this problem stems from two applications: experimental gene discovery with PCR technology and the game of Battleship (in a 1-dimensional setting). We provide adaptive algorithms for both the verification scenario (given an independent set, is it X?) and the discovery scenario (find X without any information). Under some assumptions, these algorithms use an asymptotically optimal number of queries in every instance.