Constructing disjoint paths on expander graphs

ABSTRACT

In a typical parallel or distributed computation model processors are connected by a sparse interconnection network. To establish open-line communication between pairs of processors that wish to communicate interactively, a set of disjoint paths has to be constructed on the network. Since communication needs vary in time, paths have to be dynamically constructed and destroyed. We study the complexity of constructing disjoint paths between given pairs of vertices on expander interconnection graphs. These graphs have been shown before to possess desirable properties for other communication tasks. We present a sufficient condition for the existence of &Kgr; ≤ np edge-disjoint paths connecting any set of &Kgr; pairs of vertices on an expander graph. We then show that the computational problem of constructing these paths lies in the classes Deterministic-P and Random-NC. Furthermore, we show that the set of paths can be constructed in probabilistic polylog time in the parallel-distributed model of computation, in which the n participating processors reside in the nodes of the communication graph and all communication is done through edges of the graph. Thus, the disjoint paths are constructed in the very computation model that uses them. Finally, we show how to apply variants of our parallel algorithms to find sets of vertex-disjoint paths when certain conditions are satisfied.

REFERENCES

• AKS: M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
• A: R. Aleliunas, Randomized parallel communication (Preliminary Version), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.60-72, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806683]
• Al: N. Alon, Eigenvalues and Expanders, manuscript, 1985.
• FFP: P Feldman , J Friedman , N Pippenger, Non-blocking networks, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.247-254, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12155]
• FP: J. Friedman and N. Pippenger, Expanding Graphs Contain All Small Trees, Report RJ 5145 (53485), IBM Almaden Research, May 1986.
• GJ: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• KU: A R Karlin , E Upfal, Parallel hashing—an efficient implementation of shared memory, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.160-168, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12146]
• KUW: R M Karp , E Upfal , A Wigderson, Constructing a perfect matching is in random NC, Combinatorica, v.6 n.1, p.35-48, 1986 [doi>10.1007/BF02579407]
• L: E.L. Lawler, Combinatorial Optimization' Networks and Matroids, Holt, Rinehart and Winston. 1976.
• LPS: A Lubotzky , R Phillips , P Sarnak, Explicit expanders and the Ramanujan conjectures, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.240-246, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12154]
• MVV: K. Mttlmuley, U.V. Va~ziralli and V.V. ~'azirani, Ma. tch{ng is as Easy as Matrix Inversion, Manuscript, 1985.
• P: N. Pippenger, Parallel Communication with Bounded Buffers, 25th Syrup. on Foundations of Computer Science, 1984, 127-136.
• PU: D. Peleg and U. Upfal, The Token Distribution Problem, 27th Syrup. on Foundations of Computer Science, 1986, 418-427.
• RS: N. Robertson and P.D. Seymour, Graph Minors - XIII; Vertex- Disjoint Paths, Manuscript, 1986.
• S: E. Senata, Non-negative Matrices and Markov Chains, Springer- Verlag, 1973.
• SS: E. Shamir and A. Schuster, Parallel Routing in Networks: Back to Circuit Switching?, Manuscript, 1986.
• U: Eli Upfal, Efficient Schemes for Parallel Communication, Journal of the ACM (JACM), v.31 n.3, p.507-517, July 1984 [doi>10.1145/828.1892]
• V: L. Valiant, A Scheme for Fast Parallel Communication, SLAM J. on Computing 11, (1982), 350-361.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Theory, Verification