MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer
Of course, in the answer $n$ is the number of vertices of the graph. – M P Aug 24 '10 at 18:24
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 – Aaron Aug 24 '10 at 18:26
Actually, perhaps I will just create a new question, and accept your answer -- you did answer the question I asked, after all. – Aaron Aug 24 '10 at 18:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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