Publication details

Therese Biedl, Brona Brejova, Erik D. Demaine, Angele M. Hamel, Alejandro Lopez-Ortiz, Tomas Vinar. Finding hidden independent sets in interval graphs. Technical Report CS-2001-26, University of Waterloo, December 2001.
Preprint, 295Kb | Download from publisher | BibTeX

Abstract

We design efficient competitive algorithms for discovering information
hidden by an adversary. Specifically, consider a game in a given
interval graph G in which the adversary chooses an independent set X
in G. Our 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 on the interval graph, these
algorithms use an asymptotically optimal number of queries in every
instance.