Learning a hidden uniform hypergraph

Huilan Chang*, Hung-Lin Fu, Chih Huai Shih

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Motivated by applications in genome sequencing, Grebinski and Kucherov (Discret Appl Math 88:147–165, 1998) studied the graph learning problem which is to identify a hidden graph drawn from a given class of graphs with vertex set { 1 , 2 , … , n} by edge-detecting queries. Each query tells whether a set of vertices induces any edge of the hidden graph or not. For the class of all hypergraphs whose edges have size at most r, Chodoriwsky and Moura (Theor Comput Sci 592:1–8, 2015) provided an adaptive algorithm that learns the class in O(mrlog n) queries if the hidden graph has m edges. In this paper, we provide an adaptive algorithm that learns the class of all r-uniform hypergraphs in mrlogn+(6e)rmr+12 queries if the hidden graph has m edges.

Original languageEnglish
Pages (from-to)55-62
Number of pages8
JournalOptimization Letters
Volume12
Issue number1
DOIs
StatePublished - 1 Jan 2018

Keywords

  • Adaptive algorithm
  • Complex model
  • Graph learning
  • Group testing

Fingerprint Dive into the research topics of 'Learning a hidden uniform hypergraph'. Together they form a unique fingerprint.

Cite this