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?
1 Answer
$\begingroup$
$\endgroup$
3
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 PAug 24, 2010 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$– AaronAug 24, 2010 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$– AaronAug 24, 2010 at 18:28