Here is a quick algorithmic problem: given a graph $G=(V,E)$ such that for each two distinct nodes $u,v \in V$ there's exactly one directed edge between them, and a probability $p$, such that each node is available w.p. $p$, find the maximum in-degree node in the induced realized subgraph. The goal is to minimize the expected number of queries, where a query means checking whether a node is available or not. The existence of an edge can be verified only after querying both of its end-points, of course.
Now, I am interested in proving lower bounds for either adaptive or non-adaptive sublinear time algorithms (as a function of p and n), and the complexity of constructing a policy tree that in each node either makes a query or declares the answer.
Any thoughts? Potentially useful directions would be most welcome.
Thanks, Joel.
