A problem that Mikolas bumped into.
Alice has a graph G that is closed under transitivity. Bob wants to reconstruct the graph G but Alice would only answer with YES or NO to questions of the form "is there an edge from node m to node n?". Help Bob achieve his task with as few questions as possible.
There are two possible cases. One is that Bob must aim for a minimum number of questions for the worst possible graph G. (Equivalently, Alice is evil and she keeps changing the portions of the graph G she didn't "commit" to yet, just so that Bob needs to ask more questions.) The other is that Bob aims for an expected minimum, thinking that Alice drew the graph randomly from some bag of graphs. (In the simplest case the bag is a set of all possible graphs.)
The number of nodes N is known in advance to Bob.