Incremental Algorithm for Minimum Cut and Edge Connectivity in Hypergraph

摘要

For an uncapacitated hypergraph H = (V, E) with n = |V|, m = |E| and p = Σ_(e ∈ E)|e|, and edge connectivity λ, this paper presents an insertion-only algorithm which updates minimum cut and edge connectivity incrementally on addition of a set of hyperedges to an existing hypergraph. The algorithm is deterministic and takes O(λn) amortized time per insertion of a hyperedge. The algorithm can answer queries on edge-connectivity in O(1) time and returns a cut of size λ in O(n) time. First we propose a method to maintain a hypercactus [3] under the addition of a set of hyperedges. It is observed that the time for maintaining a hypercactus on addition of a set U of hyperdeges is O(n + p_u) where p_u = Σ_(e ∈ U)|e|. This method is then used as a subroutine in our incremental algorithm for maintaining minimum cut and edge connectivity.