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.
Any pointers?
2 comments:
If I'm reading it correctly, "worst possible graph" part is not very interesting. The worst graph is with no edges and Bob will have to ask as many questions as possible edges there are. (I don't think that is equivalent to an evil opponent.)
You could also have an expected minimum on one graph. Whatever criteria you will come up to, some potential edges will be indistinguishable under those criteria and you will have to pick on random.
After Bob got N answers from Alice he must decide what is the next question. The N answers leave a number of possible graphs among which one must be found. Now, Bob might have two aims: minimize the expected number of questions until the graph is identified, or minimize the worst case. The two algorithms are different. This is what worst case and average case means for online algorithms IIRC.
Post a Comment
Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.