<p>I have a transitive DAG G which is a subgraph of an unknown DAG R.  (The nodes are the same in G and R, but R may have edges not in G.)  I can determine the presence of a given edge in R by an oracle query.</p>

<p>Many natural questions come to mind.  I've found it's often more useful to give several than just one&mdash;I wouldn't want to reject the answer I don't yet know is the right one by being over-specific upfront.</p>

<ol start="3">
<li>What is the minimum query complexity for determining R, in terms of the number of nodes and number of edges in G?</li>
<li>What is the minimum query complexity for proving that G = R if that is the case?</li>
<li>Give an algorithm for determining which edge to query at each step?  Ideally it would have decent (less than exponential... hopefully polynomial) time requirements in addition to minimizing queries.</li>
</ol>

<p>The algorithms used may be adaptive.</p>

<p>Here's (transitive reduction of) an example of a graph of the sort I'd test.  As a simpler version of #1 or #2, what's the complexity for this graph?
<a href="http://crg4.com/G.png" rel="nofollow noreferrer">sample graph http://crg4.com/G.png</a></p>

CC BY-SA 3.0
2011-09-07T04:00:36.780Z
is the relation the transitive closure of the DAG ?
Suresh Venkat
CC BY-SA 3.0
2011-09-07T04:09:55.787Z
Can I rephrase your question like this: You have a transitive DAG G. There is a transitive DAG R (the relation), which you have access to via an oracle. The given graph G is known to be a subgraph of R. You want to know the minimum queries to determine the entire graph R.
Robin Kothari
CC BY-SA 3.0
2011-09-07T04:12:54.360Z
I am also confused about (3): why would you be removing nodes ?
Suresh Venkat
CC BY-SA 3.0
2011-09-07T04:19:12.420Z
One thought is the following. Your graph is connected, and so the only interesting questions center around how the various sinks are connected. Consider merely the question of which sinks have directed edges to other sinks. It seems to me that you should be able to encode undirected graph connectivity lower bounds in the cell probe model for this case, suggesting that you might need $\Omega(n^2)$ queries for some choices of G and R using standard evasiveness arguments.
Suresh Venkat
CC BY-SA 3.0
2011-09-07T04:25:05.233Z
@Suresh: It's only connected, not strongly connected -- no multiple edges or cycles.  A -> B -> C is different from A -> C, B -> C.
Charles
CC BY-SA 3.0
2011-09-07T04:25:42.003Z
@Robin Kothari: Rewritten.
Charles
CC BY-SA 3.0
2011-09-07T04:27:50.750Z
@Charles: Yes I'm aware of that. my point is that even if you only focus on the interactions between the sinks, you should be able to embed a hard problem inside
Suresh Venkat
CC BY-SA 3.0
2011-09-07T13:24:18.160Z
Let there be n vertices. Let G have arcs from vertex 1 to all other vertices and no other arcs. Now if we want to check if G = R, then we must query every edge between vertex i and j where i and j are distinct (and not equal to 1). This shows that we need to make at least (n-1)(n-2) queries, which is $\Omega(n^2)$.
Robin Kothari
<ds.algorithms><graph-theory><graph-algorithms><query-complexity>
Discovering a graph with minimal oracle queries
Charles
# Discovering a graph with minimal oracle queries

(Asked by: username_0 on 2011-09-07)

I have a transitive DAG G which is a subgraph of an unknown DAG R. (The nodes are the same in G and R, but R may have edges not in G.) I can determine the presence of a given edge in R by an oracle query.

Many natural questions come to mind. I've found it's often more useful to give several than just one—I wouldn't want to reject the answer I don't yet know is the right one by being over-specific upfront.

3. What is the minimum query complexity for determining R, in terms of the number of nodes and number of edges in G?
4. What is the minimum query complexity for proving that G = R if that is the case?
5. Give an algorithm for determining which edge to query at each step? Ideally it would have decent (less than exponential... hopefully polynomial) time requirements in addition to minimizing queries.

The algorithms used may be adaptive.

Here's (transitive reduction of) an example of a graph of the sort I'd test. As a simpler version of #1 or #2, what's the complexity for this graph?
[sample graph http://crg4.com/G.png](http://crg4.com/G.png)

**Tags:** ds.algorithms, graph-theory, graph-algorithms, query-complexity

> **Comments:**
> **username_1**: is the relation the transitive closure of the DAG ?  
> **username_2**: Can I rephrase your question like this: You have a transitive DAG G. There is a transitive DAG R (the relation), which you have access to via an oracle. The given graph G is known to be a subgraph of R. You want to know the minimum queries to determine the entire graph R.  
> **username_1**: I am also confused about (3): why would you be removing nodes ?  
> **username_1**: One thought is the following. Your graph is connected, and so the only interesting questions center around how the various sinks are connected. Consider merely the question of which sinks have directed edges to other sinks. It seems to me that you should be able to encode undirected graph connectivity lower bounds in the cell probe model for this case, suggesting that you might need $\Omega(n^2)$ queries for some choices of G and R using standard evasiveness arguments.  
> **username_0**: @Suresh: It's only connected, not strongly connected -- no multiple edges or cycles.  A -> B -> C is different from A -> C, B -> C.  
> **username_0**: @username_2: Rewritten.  
> **username_1**: @username_0: Yes I'm aware of that. my point is that even if you only focus on the interactions between the sinks, you should be able to embed a hard problem inside  
> **username_2**: Let there be n vertices. Let G have arcs from vertex 1 to all other vertices and no other arcs. Now if we want to check if G = R, then we must query every edge between vertex i and j where i and j are distinct (and not equal to 1). This shows that we need to make at least (n-1)(n-2) queries, which is $\Omega(n^2)$.  

---

## 0 answers

