2026-07-26T01:20:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2239 2024-03-06T11:08:52Z ddc:004 open_access

Rounds in Combinatorial Search Wiener, Gábor Search group testing adaptiveness hypergraph trace The search complexity of a separating system ${cal H} subseteq 2^{[m]}$ is the minimum number of questions of type ``$xin H$? hinspace '' (where $H in {cal H}$) needed in the worst case to determine a hidden element $xin [m]$. If we are allowed to ask the questions in at most $k$ batches then we speak of the emph{$k$-round} (or emph{$k$-stage}) complexity of ${cal H}$, denoted by $hbox{c}_k ({cal H})$. While $1$-round and $m$-round complexities (called non-adaptive and adaptive complexities, respectively) are widely studied (see for example Aigner cite{A}), much less is known about other possible values of $k$, though the cases with small values of $k$ (tipically $k=2$) attracted significant attention recently, due to their applications in DNA library screening. It is clear that $ |{cal H}| geq hbox{c}_{1} ({cal H}) geq hbox{c}_{2} ({cal H}) geq ldots geq hbox{c}_{m} ({cal H})$. A group of problems raised by {G. O. H. Katona} cite{Ka} is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems ${cal H}$ with the property $|{cal H}| = hbox{c}_{k} ({cal H}) $ for any $kgeq 3$. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gábor Wiener 2009 Is Part Of Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.09281.6 urn:nbn:de:0030-drops-22399 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.6 eng https://creativecommons.org/licenses/by/4.0/legalcode