# Network Reconstruction from Flow Function

Suppose that $T$ is a set of vertices in an unknown network. We have oracle $F(X,Y)$ that returns maximum flow value between $X, Y \subseteq T$ in the unknown network.

Can we reconstruct the unknown network by calling this oracle polynomially-many times? More precisely, can we construct a network whose flow function is consistent with the given oracle?

Example: $T = \{a,b,c\}$, $F(a,bc) = F(b,ac) = F(c,ab) = 1$. Then both "triangle $K_3$ whose edge weights are $1/2$" and "3-star $S_3$ whose edge weights are $1$" are solutions.

• To give a "No" answer, it would suffice to find 2 (families of) networks that can only be distinguished with a superpolynomial number of queries. So I think a "Yes" answer would be surprising, since it would imply that, after querying the oracle polynomially many times, all of its remaining answers are forced. – j_random_hacker Aug 13 '17 at 14:44
• To clarify: when you say "the maximum flow value between $X, Y \subseteq T$", are you taking the maximum over all $(x, y)$ pairs such that $x \in X$, $y \in Y$, $x$ is the source and $y$ is the sink? Because it would then seem possible that the optimal $x$ and $y$ vary across different queries (choices of $X$ and $Y$). I think this could make it easier to prove a "No" answer. – j_random_hacker Aug 13 '17 at 15:06
• @j_random_hacker "maximum flow between X, Y" is the multi-source multi-sink maximum flow, which is equivalent to the maximum frow from supersource $s$ to supersink $t$ where $(s,x)$ ($x \in X$) and $(y,t)$ ($y \in Y$) are added. – mhtk Aug 14 '17 at 14:07
• OK, and are these added edges infinite-capacity? If so, the maximum flow from $X$ to $Y$ is simply the sum of the capacities of all edges in the cut. (Meaning that the structure of the graph induced by $X$ or by $Y$ is irrelevant, which makes the problem a bit simpler.) – j_random_hacker Aug 14 '17 at 17:55
• @j_random_hacker Yes, these have infinity capacities. – mhtk Aug 14 '17 at 22:54