Inverse polymatroidal flow problem

Let D = (V, A) be a directed graph, for each vertex v is an element of V, l et Delta(+)(upsilon) and Delta(-)(upsilon) denote the sets of arcs leaving and entering upsilon, F-upsilon(+) and F-upsilon(-) be intersecting familie s on Delta(+)(upsilon) and Delta(-)(upsilon), respectively, and rho(upsilon )(+) : F-upsilon(+) --> R+ and rho(upsilon)(-) : F-upsilon(+) --> R+ be sub modular functions on intersecting pairs. A flow f : A --> R is feasible if f(Delta(+)(upsilon)) = f(Delta-(upsilon)) For All upsilon is an element of V, f(S) less than or equal to rho(upsilon)(+)(S) For All S is an element of F- upsilon(+), upsilon is an element of V, f(S) less than or equal to rho(upsilon)(-)(S) For All S is an element of F- upsilon(-), upsilon is an element of V, f(e) greater than or equal to 0 For All e is an element of A, Given a cost function c on A, the minimum cost polymatroidal flow problem i s to find a feasible flow f with minimum cost Sigma{c(e)f(e) \ e is an elem ent of A}, it is a significant generalization of many combinatorial optimiz ation problems. Given a feasible flow f*, cost and restriction functions on A, the inverse polymatroidal flow problem is to modify c, optimally and with bounds, such that f* becomes a minimum cost polymatroidal flow under the modified cost. It is shown in this paper that the inverse problem can be formulated as a c ombinatorial linear program and can be further transformed into a minimum c ost circulation problem. Hence it can be solved efficiently by strongly pol ynomial combinatorial algorithms. We also give a necessary and sufficient c ondition for the feasibility of the inverse problem.