When: Sunday, April 16,
10am
Where: Schreiber 309
Speaker: Ohad
Noy Feldheim, Hebrew University
Title:
Min-Cost-Flow Preserving Bijection Between Subgraphs and Orientations
In 2013, Kozma and Moran showed, using VC-dimension arguments, that the number of subgraphs of a given graph $G=(V,E)$ which $k$-connect a vertex $v$ to a vertex $u$ is the same as the number of orientations with the same property. Their proof is, however, non-constructive in nature, and the naive construction that could be derived from it, is exponential in $|V|$ even for fixed values of $k$. We provide an alternative constructive proof, using flow arguments, which generalises this result to weighted graphs and to general flow constraints, show that the bijection preserves the minimum cost flow, and recover the bijection in $O(|E||V|^2\log|V|)$ time.