Abstract In computing with explorable uncertainty, one considers problems where the values of some input elements are uncertain, typically represented as intervals, but can be obtained using queries. Previous work has considered query minimization in the settings where queries are asked sequentially (adaptive model) or all at once (non-adaptive model). We introduce a new model where k queries can be made in parallel in each round, and the goal is to minimize the number of query rounds. Using competitive analysis, we present upper and lower bounds on the number of query rounds required by any algorithm in comparison with the optimal number of query rounds for the given instance. Given a set of uncertain elements and a family of m subsets of that set, we study the problems of sorting all m subsets and of determining the minimum value (or the minimum element(s)) of each subset. We also study the selection problem, i.e., the problem of determining the i-th smallest value and identifying all elements with that value in a given set of uncertain elements. Our results include 2-round-competitive algorithms for sorting and selection and an algorithm for the minimum value problem that uses at most $$(2+\varepsilon ) \cdot \mathrm {opt}_k+\mathrm {O}\left( \frac{1}{\varepsilon } \cdot \lg m\right) $$ ( 2 + ε ) · opt k + O 1 ε · lg m query rounds for every $$0<\varepsilon <1$$ 0 < ε < 1 , where $$\mathrm {opt}_k$$ opt k is the optimal number of query rounds.

Consider the problem of discovering (or verifying) the edges and non-edges of a network, modeled as a connected undirected graph, using a minimum number of queries. A query at a vertex v discovers (or verifies) all edges and non-edges whose endpoints have different distance from v. In the network discovery problem, the edges and non-edges are initially unknown, and the algorithm must select the next query based only on the results of previous queries. We study the problem using competitive analysis and give a randomized on-line algorithm with competitive ratio $O(\sqrt{nlogn})$ for graphs with n vertices. We also show that no deterministic algorithm can have competitive ratio better than 3. In the network verification problem, the graph is known in advance and the goal is to compute a minimum number of queries that verify all edges and non-edges. This problem has previously been studied as the problem of placing landmarks in a graph or determining the metric dimension of a graph. We show that there is no approximation algorithm for this problem with ratio o(log n) unless $\mathcal{P} = \mathcal{NP}$ .