Computing Edge-Connectivity in Multigraphs and Capacitated Graphs

TLDR

Edge‑connectivity of an undirected graph can be computed by solving O(|V|) max‑flow problems, with best known time bounds O(λ|V|²) for simple graphs and O(|E|^{3/2}|V|) for multigraphs. The authors propose an O(|E| + min{λ|V|², p|V| + |V|² log|V|}) time algorithm for computing the edge‑connectivity of a multigraph. The algorithm avoids max‑flow by performing |V| graph searches and edge contractions, and extends to capacitated networks to compute minimum cut capacity in O(|V||E| + |V|² log|V|) time.

Abstract

Given an undirected graph $G = ( V,E )$, it is known that its edge-connectivity $\lambda ( G )$ can be computed by solving $O( | V | )$ max-flow problems. The best time bounds known for the problem are $O( \lambda ( G ) | V |^2 )$, due to Matula (28th IEEE Symposium on the Foundations of Computer Science, 1987, pp. 249–251) if G is simple, and $O( | E |^{3/2} | V | )$, due to Even and Tarjan (SIAM J. Comput., 4 (1975), pp. 507–518) if G is multiple. An $O( | E | + \min \{ \lambda ( G ) | V |^2 ,p | V | + | V |^2 \log | V | \} )$ time algorithm for computing the edge-connectivity $\lambda ( G )$ of a multigraph $G = ( V,E )$, where $p ( \leqq | E | )$ is the number of pairs of nodes between which G has an edge, is proposed. This algorithm does not use any max-flow algorithm but consists only of $| V |$ times of graph searches and edge contractions. This method is then extended to a capacitated network to compute its minimum cut capacity in $O ( | V | | E | + | V |^2 \log | V | )$ time.