**Reference**:- Therese Biedl, Broňa Brejová, Erik D. Demaine, Angèle M. Hamel, Alejandro López-Ortiz, and Tomáš Vinař, “Finding Hidden Independent Sets in Interval Graphs”, in
*Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003)*, Big Sky, Montana, July 25–28, 2003, pages 182–191. **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 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. **Length**:- The paper is 10 pages.
**Availability**:- The paper is available in PostScript (199k) and gzipped PostScript (76k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- PCR_TCS (Finding Hidden Independent Sets in Interval Graphs)
- PCR_TR2001 (Finding Hidden Independent Sets in Interval Graphs)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.