Finding strongly connected components in parallel using O(log2n) reachability queries

ABSTRACT

We give a randomized (Las-Vegas) parallel algorithm for computing strongly connected components of a graph with n vertices and m edges. The runtime is dominated by O(log²n) multi-source parallel reachability queries; i.e. O(log²n) calls to a subroutine that computes the union of the descendants of a given set of vertices in a given digraph. Our algorithm also topologically sorts the strongly connected components.

Using Ullman and Yannakakis's [22] techniques for the reachability subroutine gives our algorithm runtime Õ(t) using mn/t² processors for any (n²/m)^1/3 ≤= t ≤= n. On sparse graphs, this improves the number of processors needed to compute strongly connected components and topological sort within time n^1/3 ≤= t ≤= n from the previously best known (n/t)³ [20] to (n/t)².

REFERENCES

• 1: Alok Aggarwal , Richard J. Anderson , Ming-Yang Kao, Parallel depth-first search in general directed graphs, SIAM Journal on Computing, v.19 n.2, p.397-409, April 1990 [doi>10.1137/0219025]
• 2: D. Bader. A practical parallel algorithm for cycle detection in partitioned digraphs. Technical Report AHPCC-TR-99-013, Electrical & Computer Eng. Dept., Univ. New Mexico, Albuquerque, NM, 1999.
• 3: Roderick Bloem , Harold N. Gabow , Fabio Somenzi, An Algorithm for Strongly Connected Component Analysis in n log n Symbolic Steps, Formal Methods in System Design, v.28 n.1, p.37-56, January 2006 [doi>10.1007/s10703-006-4341-z]
• 4: Edith Cohen, Size-estimation framework with applications to transitive closure and reachability, Journal of Computer and System Sciences, v.55 n.3, p.441-453, Dec. 1997 [doi>10.1006/jcss.1997.1534]
• 5: D. Coppersmith, L. Fleischer, B. Hendrickson, and A. Pinar. A divide-and-conquer algorithm for identifying strongly connected components. Technical Report RC23744, IBM Research, 2005.
• 6: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• 7: Lisa Fleischer , Bruce Hendrickson , Ali Pinar, On Identifying Strongly Connected Components in Parallel, Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing, p.505-511, May 01-05, 2000
• 8: Hillel Gazit , Gary L. Miller, An improved parallel algorithm that computes the BFS numbering of a directed graph, Information Processing Letters, v.28 n.2, p.61-65, June 24, 1988 [doi>10.1016/0020-0190(88)90164-0]
• 9: Raffaella Gentilini , Carla Piazza , Alberto Policriti, Computing strongly connected components in a linear number of symbolic steps, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 10: John Greiner, A comparison of parallel algorithms for connected components, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.16-25, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181021]
• 11: Ming-Yang Kao, Linear-processor NC algorithms for planar directed graphs I: strongly connected components, SIAM Journal on Computing, v.22 n.3, p.431-459, June 1993 [doi>10.1137/0222032]
• 12: M.-Y. Kao , P. N. Klein, Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.181-192, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100237]
• 13: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 14: William Mclendon, III , Bruce Hendrickson , Steve Plimpton , Lawrence Rauchwerger, Finding strongly connected components in parallel in particle transport sweeps, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.328-329, July 2001, Crete Island, Greece [doi>10.1145/378580.378751]
• 15: William McLendon, III , Bruce Hendrickson , Steven J. Plimpton , Lawrence Rauchwerger, Finding strongly connected components in distributed graphs, Journal of Parallel and Distributed Computing, v.65 n.8, p.901-910, August 2005 [doi>10.1016/j.jpdc.2005.03.007]
• 16: Michael Mitzenmacher , Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, New York, NY, 2005
• 17: Steve Plimpton , Bruce Hendrickson , Shawn Burns , Will McLendon, III, Parallel algorithms for radiation transport on unstructured grids, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.25-es, November 04-10, 2000, Dallas, Texas, United States
• 18: S. Rajasekaran , J. H. Reif, Optimal and sublogarithmic time randomized parallel sorting algorithms, SIAM Journal on Computing, v.18 n.3, p.594-607, June 1989 [doi>10.1137/0218041]
• 19: J. H. Reif. Depth-first search is inherently sequential. Information Processing Letters, 20(5):229--234, 1985.
• 20: Thomas H. Spencer, Time-work tradeoffs for parallel algorithms, Journal of the ACM (JACM), v.44 n.5, p.742-778, Sept. 1997 [doi>10.1145/265910.265923]
• 21: R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1:146--160, 1972.
• 22: Jeffrey D. Ullman , Mihalis Yannakakis, High probability parallel transitive-closure algorithms, SIAM Journal on Computing, v.20 n.1, p.100-125, Feb. 1991 [doi>10.1137/0220006]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
graph algorithms, parallel algorithms, strongly connected components, topological sort, transitive closure bottleneck