CS Theory Seminar

Computing the connectivity (also known as unweighted maximum flow) between nodes in a network is a foundational problem in combinatorial optimization. In general dense graphs, the current fastest algorithm for computing connectivities between all pairs of nodes is the naïve approach, where one simply runs an almost-linear time maximum flow algorithm separately for each pair of vertices. In this talk, we discuss faster algorithms computing all-pairs connectivities in sparse graphs and for bounded connectivity values. These approaches bypass the machinery of fast max-flow entirely, and instead are based off classic techniques for enumerating lattice paths using determinants.