Paper Info
Title
Combinatorial search in two and more rounds
Abstract
In a combinatorial search problem we wish to identify an unknown element by binary tests, where the edges of a hypergraph specify the available tests. We show that, for rather general cases of this problem, the worst-case minimum number of tests, even if adaptive testing is permitted, can already be achieved in a small number of rounds of parallel tests. In particular, the maximum number of necessary rounds grows only as the square root of the number of elements, and two rounds are enough if, e.g., the test number is close to the number of elements, or the hypergraph is a graph. We also provide polynomial-time, hardness, and parameterized results on the computational complexity of finding optimal strategies for some cases, including graphs and tree hypergraphs.
Year
DOI
Venue
2019
10.1016/j.tcs.2019.02.004
Theoretical Computer Science
Keywords
Field
DocType
Combinatorial search,Test cover,Adaptive strategy,Matching
Small number,Discrete mathematics,Combinatorics,Parameterized complexity,Hypergraph,Constraint graph,Square root,Combinatorial search,Mathematics,Computational complexity theory,Binary number
Journal
Volume
ISSN
Citations 
780
0304-3975
0
PageRank 
References 
Authors
0.34
11
1
Name
Order
Citations
PageRank
Peter Damaschke147156.99