Return to Revisions

Generally $k$-connectivity is computed using max-flow min-cut algorithms. I cannot quote you complexities off the top of my head, but you should be able to find the number of edges that disconnect any pair of nodes $(x,y)$, and then iterate over all $O(n^2)$ pairs. A key result here that underpins these algorithms is Menger's Theorem.