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.

  • $\begingroup$ Is the graph G known before you prepare a policy tree? And is it required to find the exact maximum degree node, or are you allowing your answer to be an approximation? Because even if G is known, if you require exact answers then sublinear expected time seems unlikely to me. $\endgroup$ – David Eppstein Jun 13 '12 at 6:34
  • $\begingroup$ Thanks David. Yes, we do know the underlying graph (just not the realized subgraph). $\endgroup$ – JoelO Jun 13 '12 at 21:30
  • $\begingroup$ The option of approximating the maximum degree node indeed sounds like the best direction. There are few possible questions I can think of: 1) What is the complexity of constructing a policy tree with the minimal expected complexity.In general the tree can reach exponential size,so NP-hardness seems inappropriate. 2) We can take a non-adaptive route, by asking what is the ordering of nodes that will minimize the expected number of queries. 3) We can find a example in which there are a few nodes with high degrees, and determining the winner among them requires a linear # of queries. $\endgroup$ – JoelO Jun 13 '12 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.