Reproduce “Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, Nikos Parotsidis

Researchers developed algorithms that compute maximal 2-edge-connected and 2-vertex-connected subgraphs in sparse directed graphs in O(m^(3/2)) time, improving upon prior O(n^2) and O(mn) methods. This work also extends to k-edge-connected subgraphs for constant k, achieving O(m^(3/2) log n) time.

Key insights

  • Efficiently identifying "small" k-out/in components using localized searches enables a divide-and-conquer approach that is particularly effective for sparse directed graphs.
  • The optimal parameter Δ = √m balances the cost of local searches with the depth of recursion, leading to the O(m^(3/2)) complexity bound.
  • A two-phase DFS (involving path reversal for edges or vertex blocking for vertices) allows for the efficient detection of small 1-edge-out or 1-vertex-out components in linear time with respect to their size.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.