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