Given an unweighted graph $G = (V, E)$, let the cut function on this graph be defined to be: $C:2^V \rightarrow \mathbb{Z}$ such that: $$C(S) = |\{(u,v) \in E : u \in S \wedge v \not\in S\}|$$ Suppose you have the ability to query $C$, but otherwise have no knowledge of the edge set $E$. Is it possible to reconstruct $G$ by making only polynomial (in $|V|$) many queries to the cut function?


Asking individual vertices, you figure out the valence of each vertex with $n$ questions. Asking for pairs of vertices, you can then decide if each pair has an edge between them or not: they have an edge if and only if the "degree" on the pair is two less than the sum of the "degrees". Thus you can reconstruct the graph with $n+\binom{n}{2}$ questions.

  • $\begingroup$ Of course, in the answer $n$ is the number of vertices of the graph. $\endgroup$
    – M P
    Aug 24 '10 at 18:24
  • $\begingroup$ Thanks -- of course you are correct! I have obviously oversimplified the question I am interested in. I will revise to make the question less trivial $\endgroup$
    – Aaron
    Aug 24 '10 at 18:26
  • 3
    $\begingroup$ Actually, perhaps I will just create a new question, and accept your answer -- you did answer the question I asked, after all. $\endgroup$
    – Aaron
    Aug 24 '10 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.