Uniqueness of minimum cost flow and reduced cost optimality condition

182 Views Asked by At

Let $G = (V, E)$ be a directed graph with edge costs $c: E \rightarrow \mathbb{Z}_{\geq 0}$ and edge capacities $w: E \rightarrow \mathbb{Z}_{\geq 0}$. Let $f^*: E \rightarrow \mathbb{R}_{\geq 0}$ be a minimum cost flow, $\pi$ be a set of node labels or potentials such that $c^{\pi}((u,v)) = c((u,v)) - \pi(u) + \pi(v) \geq 0$. Let $G^{0}_{f^*}$ be the subgraph consisting of only edges of the residual graph $G_{f^*}$ with $c^{\pi}((u,v)) = 0$. How can I go about proving that $f^*$ is the unique minimum cost flow iff $G^{0}_{f^*}$ has a directed cycle with length of at least 3. I am aware that this question: Nonzero Reduced Cost in Linear Programming Optimal Solution Implies Uniqueness of Optimum? is a more general version of mine but I would like to solve this problem without looking too deep into Linear Programming. Any help is appreciated.