Inverse Polymatroidal Flow Problem

Let D = (V, A) be a directed graph, for each vertex v ∈ V, let Δ+(v) and Δ− (v) denote the sets of arcs leaving and entering v, $${\mathcal{F}}_v^ +$$ and $${\mathcal{F}}_v^ -$$ be intersecting families on Δ+(v) and Δ−(v), respectively, and $$\rho _v^+ :{\mathcal{F}}_v^+ \to {\mathcal{R}}_+$$ and $$\rho_v^- :{\mathcal{F}}_v^+ \to {\mathcal{R}}_+$$ be submodular functions on intersecting pairs. A flow f : A → R is feasible if $$\begin{gathered} f(\Delta ^ + (v)) = f(\Delta ^ - (v)){\text{ }}\forall v \in V,\hfill \\ f(S) \leqslant \rho _v^ + (S){\text{ }}\forall S \in \mathcal{F}_v^+ ,v \in V, \hfill \\ f(S) \leqslant \rho _v^ - (S){\text{ }}\forall S \in \mathcal{F}_v^- ,v \in V, \hfill \\ f(e) \geqslant 0{\text{ }}\forall e \in A, \hfill \\\end{gathered}$$ Given a cost function c on A, the minimum cost polymatroidal flow problem is to find a feasible flow f with minimum cost σ{c(e)f(e)ve σ A}, it is a significant generalization of many combinatorial optimization 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 combinatorial linear program and can be further transformed into a minimum cost circulation problem. Hence it can be solved efficiently by strongly polynomial combinatorial algorithms. We also give a necessary and sufficient condition for the feasibility of the inverse problem.