Computational Biology
@ Comenius University in Bratislava

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.

Download preprint: 01pcr.ps, 295Kb

Download from publisher: not available

Related web page: not available

Bibliography entry: BibTeX

See also: early version

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.