Talk information

Date: Sunday, April 16, 2023
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Ohad Feldheim (HUJI)
Title: Min-cost-flow preserving bijection between subgraphs and orientations

Abstract:

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.

Joint work with Izhak Elmaleh.