Min-cost-flow preserving bijection between subgraphs and orientations (Q2111782)

Summary: Consider an undirected graph \(G=(V, E)\). A subgraph of \(G\) is a subset of its edges, while an orientation of \(G\) is an assignment of a direction to each of its edges. Provided with an integer circulation-demand \(d:V\to \mathbb{Z}\), we show an explicit and efficiently computable bijection between subgraphs of \(G\) on which a \(d\)-flow exists and orientations on which a \(d\)-flow exists. Moreover, given a cost function \(w:E\to (0,\infty)\) we can find such a bijection which preserves the \(w\)-min-cost-flow. In [Electron. J. Comb. 20, No. 3, Research Paper P44, 18 p. (2013; Zbl 1298.05145)], \textit{L. Kozma} and \textit{S. Moran} showed, using dimensional methods, that the number of subgraphs \(k\)-edge-connecting a vertex \(s\) to a vertex \(t\) is the same as the number of orientations \(k\)-edge-connecting \(s\) to \(t\). An application of our result is an efficient, bijective proof of this fact.