Efficient algorithm for computing all low s-t edge connectivities in directed graphs

Abstract

Given a directed graph with n nodes and m edges, the (strong) edge connectivity λ (u; v) between two nodes u and v is the minimum number of edges whose deletion makes u and v not strongly connected. The problem of computing the edge connectivities between all pairs of nodes of a directed graph can be done in O(m ω) time by Cheung, Lau and Leung (FOCS 2011), where ω is the matrix multiplication factor (≈ 2:373), or in Õ (mn1:5) time using O(n) computations of max-flows by Cheng and Hu (IPCO 1990). We consider in this paper the “low edge connectivity” problem, which aims at computing the edge connectivities for the pairs of nodes (u; v) such that λ (u; v) ≤ k. While the undirected version of this problem was considered by Hariharan, Kavitha and Panigrahi (SODA 2007), who presented an algorithm with expected running time Õ (m+nk3), no algorithm better than computing all-pairs edge connectivities was proposed for directed graphs. We provide an algorithm that computes all low edge connectivities in O(kmn) time, improving the previous best result of O (min(m ω, mn1:5)) when k ≤ √ n. Our algorithm also computes a minimum u-v cut for each pair of nodes (u; v) with λ (u; v) ≤ k.