Min-Cost-Flow Problem

Question

Given a directed graph $G = (V,E)$ with a cost function $\gamma: E \to \Bbb R_{\geq 0}$ and two vertices $u,v \in V$.

How to reduce the problem of finding a directed path from $u$ to $v$ with minimum cost to the Min-Cost-Flow Problem with some capacity, demand, cost functions?

Thank you.

Answer 1

Hint:

1. Create $G'$ as follows:
   • For any $w \in V$ create two vertices $w_\text{in}$ and $w_\text{out}$. Connect them with an edge of zero cost.
   • For any $e \in E$ create two vertices $e_\text{in}$ and $e_\text{out}$. Connect them with an edge of zero cost.
   • For any $e = (w \to w') \in E$ add edges $\{w_\text{out},e_\text{in}\}$ and $\{e_\text{out}, w'_\text{in}\}$ both of cost $\frac{1}{2}\gamma(e)$.
   • Remove $u_\text{in}$ and $v_\text{out}$.
2. Why is $G'$ bipartite?
3. Using min-cost-flow find the min-cost perfect matching in $G'$.
4. Why any perfect matching in $G'$ indicates a path from $u$ to $v$ in $G$?
5. What happens if there is no path $u \to^* v$ in $G$?

I hope this helps $\ddot\smile$