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.

  1. What is the minimum query complexity for determining R, in terms of the number of nodes and number of edges in G?
  2. What is the minimum query complexity for proving that G = R if that is the case?
  3. 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

  • $\begingroup$ is the relation the transitive closure of the DAG ? $\endgroup$ – Suresh Venkat Sep 7 '11 at 4:00
  • 2
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Sep 7 '11 at 4:09
  • $\begingroup$ I am also confused about (3): why would you be removing nodes ? $\endgroup$ – Suresh Venkat Sep 7 '11 at 4:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Sep 7 '11 at 4:19
  • $\begingroup$ @Suresh: It's only connected, not strongly connected -- no multiple edges or cycles. A -> B -> C is different from A -> C, B -> C. $\endgroup$ – Charles Sep 7 '11 at 4:25

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.