Finding hidden independent sets in interval graphs

✍ Scribed by Therese Biedl; Broňa Brejová; Erik D. Demaine; Angèle M. Hamel; Alejandro López-Ortiz; Tomáš Vinař

• Book ID: 104325931
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 301 KB
• Volume: 310
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00422-5

✦ Synopsis

We design e cient competitive algorithms for discovering hidden information using few queries. Speciÿcally, consider a game in a given set of intervals (and their implied interval graph G) in which our goal is to discover an (unknown) 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 veriÿcation scenario (given an independent set, is it X ?) and the discovery scenario (ÿnd X without any information). Under some assumptions, these algorithms use an asymptotically optimal number of queries in every instance.