×

Constructing a perfect matching is in random NC. (English) Zbl 0646.05051

Summary: We show that the problem of constructing a perfect matching in a graph is in the complexity class random NC; i.e., the problem is solvable in polylog time by a randomized parallel algorithm using a polynomial- bounded number of processors. We also show that several related problems lie in random NC. These include: (i) Constructing a perfect matching of maximum weight in a graph whose edge weights are given in unary notation; (ii) Constructing a maximum-cardinality matching; (iii) Constructing a matching covering a set of vertices of maximum weight in a graph whose vertex weights are given in binary; (iv) Constructing a maximum s-t flow in a directed graph whose edge weights are given in unary.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Angluin andL. G. Valiant, Fast probabilistic algorithms for Hamiltonian circuits and matchings.J. of Comp. Syst. Sci. 18 (1979), 155–193. · Zbl 0437.05040 · doi:10.1016/0022-0000(79)90045-X
[2] A. Borodin, S. A. Cook andN. Pippenger, Parallel computation for well-endowed rings and space bounded probabilistic machines.Information and Control 58 (1983), 113–136. · Zbl 0598.68043 · doi:10.1016/S0019-9958(83)80060-6
[3] A. Borodin, J. von zur Gathen andJ. Hopcroft, Fast parallel matrix and GCD computations.Proc. 23 STOC (1982), 65–71. · Zbl 0507.68020
[4] S. A. Cook, An overview of computation complexity.CACM 26 (1983), 400–408. · Zbl 0622.68039
[5] J. Edmonds, Systems of distinct representatives and linear algebra.J. of Res. Nat. Bureau of Standards,71 A (1967), 241–245. · Zbl 0178.03002
[6] J. Edmonds andR. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems.J. of ACM 19 (1972), 248–264. · Zbl 0318.90024 · doi:10.1145/321694.321699
[7] L. M. Goldschlager, R. A. Shaw andJ. Staples, The maximum flow problem is logspace complete for P.Theoretical Computer Science 21 (1982), 105–111. · Zbl 0486.68035 · doi:10.1016/0304-3975(82)90092-5
[8] H. J. Karloff, A Las Vegas RNC algorithm for maximum matchingCombinatorica, to appear. · Zbl 0646.05050
[9] R. M. Karp, E. Upfal andA. Wigderson, Are search and decision problems computationally equivalent?STOC 1985.
[10] D. Kozen, U. V. Vazirani andV. V. Vazirani, The two-processors scheduling problem is in R-NC.STOC 1985. · Zbl 0598.68050
[11] L. Lovász, Determinants, matchings and random algorithms,in: Fundamentals of Computation Theory, FCT’79. (ed. L. Budach), Akademie-Verlag Berlin 1979, pp 565–574.
[12] M. O. Rabin andV. V. Vazirani, Maximum matchings in general graphs through randomization, TR-15-84,Harvard University Center for Research in Computing Technology, 1984. · Zbl 0689.68092
[13] J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities.J. of ACM,27 (1980), 701–717. · Zbl 0452.68050 · doi:10.1145/322217.322225
[14] E. Shamir andE. Upfal,N-processors graphs distributively achieve perfect matching inO(log2 N) beats.Proceeding of the First ACM SIGACT-SIGMOD Symp. on Principles of Distributed Computing. Ottawa, 1982, 238–241.
[15] W. T. Tutte, The factors of graphs.Canad. J. Math. 4 (1952), 314–328. · Zbl 0049.24202 · doi:10.4153/CJM-1952-028-2
[16] D. J. A. Welsh,Matroid Theory. Academic Press (1976).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.