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. In T. Warnow, B. Zhu, ed., Computing and Combinatorics, 9th Annual International Conference, COCOON 2003, 2697 volume of Lecture Notes in Computer Science, pp. 182-191, Big Sky, MT, July 25-28 2003. Springer.

Download preprint: 03pcr.ps, 199Kb

Download from publisher: http://www.springerlink.com/link.asp?id=jyr153kk9cndvu04

Related web page: not available

Bibliography entry: BibTeX

See also: early version

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.