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 2013, Kozma and Moran [Electron. J. Comb. 20(3)] 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.
@article{10_37236_10940,
author = {Izhak Elmaleh and Ohad N. Feldheim},
title = {Min-cost-flow preserving bijection between subgraphs and orientations},
journal = {The electronic journal of combinatorics},
year = {2023},
volume = {30},
number = {1},
doi = {10.37236/10940},
zbl = {1506.05081},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10940/}
}
TY - JOUR
AU - Izhak Elmaleh
AU - Ohad N. Feldheim
TI - Min-cost-flow preserving bijection between subgraphs and orientations
JO - The electronic journal of combinatorics
PY - 2023
VL - 30
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/10940/
DO - 10.37236/10940
ID - 10_37236_10940
ER -
%0 Journal Article
%A Izhak Elmaleh
%A Ohad N. Feldheim
%T Min-cost-flow preserving bijection between subgraphs and orientations
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10940/
%R 10.37236/10940
%F 10_37236_10940
Izhak Elmaleh; Ohad N. Feldheim. Min-cost-flow preserving bijection between subgraphs and orientations. The electronic journal of combinatorics, Tome 30 (2023) no. 1. doi: 10.37236/10940
