Reverse optimization of a minimum cost flow network

Question

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$).

The cost to send $x$ unit of flow through edge $e_i$ is defined as $w_i*F(x)$, where $w_i$ is the weight of edge $e_i$. Assume that the structure of graph $(V,E)$ is given, $F(X)$ is given, but $W$ is unknown.

If you were also given a series of (approximate or exact) minimum costs $C$ to send one unit of flow between each pair of neighbor nodes $(u,v)$, where there is a $e$ in $E$ that connects $u,v$.

How do I estimate the weights $W$ on the set of edges $E$?

And if the minimum costs are approximate, there might be inconsistency in this data, how do I estimate the approximate weights W to minimize the $L^2$ or $L^1$ norm?

Is there an efficient algorithm?

Answer 1

The minimum costs does not carry enough information to reconstruct the edge weights.

Counterexample: Three vertices a, b, b W(a,b) = W(a,c) = 1 < 2 << W(a,c)

The minimum cost from a to c is 2, and as long as W(a,c) is bigger than that, you can't recover it.

There could be some dynamic protocol where you can sent far more than unit flow.