Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E). Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where |V| = n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B ⊂ V, and it requires O(n²(n - n_A - n_B)R_AB) time in this case, where n_A = |A|, n_B = |B| and R_AB is the number of all minimal A-B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_Σ is the number of all minimal separators of G and R_Σ ≤ A⁺_Σ = ∑_{1≤i≠j≤n,(vi,vj)∉E} R_vivj ≤ (n(n - 1)/2 - m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ + n log nR_Σ) on a CREW PRAM with O(n³) processors.