<p>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 <em>one</em> 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.</p>

<p>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. </p>

<p>Any thoughts? Potentially useful directions would be most welcome.</p>

<p>Thanks,
Joel.</p>

CC BY-SA 3.0
2012-06-13T06:34:03.093Z
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.
David Eppstein
CC BY-SA 3.0
2012-06-13T21:30:25.187Z
Thanks David. Yes, we do know the underlying graph (just not the realized subgraph).
JoelO
CC BY-SA 3.0
2012-06-13T21:43:41.403Z
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.
JoelO
<ds.algorithms><property-testing>
Sublinear time algorithm for maximum degree node
JoelO
# Sublinear time algorithm for maximum degree node

(Asked by: username_0 on 2012-06-12)

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.

**Tags:** ds.algorithms, property-testing
> **Comments:**
> **username_1**: 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.  
> **username_0**: Thanks David. Yes, we do know the underlying graph (just not the realized subgraph).  
> **username_0**: 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.  

---

## 0 answers

