Finding Hidden Independent Sets in Interval Graphs
[.ps]
[.pdf]
Abstract
We design efficient competitive algorithms for discovering information hidden by an adversary. Specifically, consider a game in a given interval grpah
G in which the adversary chooses an independent set
X in
G. Our ogal 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 tehcnology and the game of Battleship (in a
1-dimensional setting). We prove 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.
Bibtex Entry
