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?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
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. 

