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.

  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Aug 13 '17 at 14:44
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Aug 13 '17 at 15:06
  • $\begingroup$ @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. $\endgroup$ – mhtk Aug 14 '17 at 14:07
  • $\begingroup$ 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.) $\endgroup$ – j_random_hacker Aug 14 '17 at 17:55
  • $\begingroup$ @j_random_hacker Yes, these have infinity capacities. $\endgroup$ – mhtk Aug 14 '17 at 22:54

Your Answer

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

Browse other questions tagged or ask your own question.