Fast probabilistic algorithms for hamiltonian circuits and matchings

ABSTRACT

The main purpose of this paper is to give techniques for analysing the probabilistic performance of certain kinds of algorithms, and hence to suggest some fast algorithms with provably desirable probabilistic behaviour. The particular problems we consider are: finding Hamiltonian circuits in directed graphs (DHC), finding Hamiltonian circuits in undirected graphs (UHC), and finding perfect matchings in undirected graphs (PM). We show that for each problem there is an algorithm that is extremely fast (0(n(log n)2) for DHC and UHC, and 0(nlog n) for PM), and which with probability tending to one finds a solution in randomly chosen graphs of sufficient density. These results contrast with the known NP-completeness of the first two problems [2,12] and the best worst-case upper bound known of 0(n2.5) for the last [9].

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 3: S.A. Cook and R.A. Reckhow, Time-bounded random access machines, JCSS 7, 354-375 (1973).
• 4: G.A. Dirac, Some theorems on abstract graphs, Proc.London Math.Soc. 2, 69-81 (1952).
• 5: J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17, 449-467 (1965).
• 6: P. Erdös and A. Rényi, On random graphs I, Publicationes Mathematicae 6, 290-297 (1959).
• 7: P. Erdös and A. Rényi, On the existence of a factor of degree one of connected random graphs, Acta Math. Acad. Sci. Hung. 17, 359-379 (1966).
• 8: P. Erdös and J. Spencer, Probabilistic Methods in Combinatorics, Academic Press, New York (1974).
• 9: S. Even and O. Kariv, An 0(n2.5) algorithm for maximum matching in general graphs, Proc. IEEE 16th Symp. on FOCS, 100-112 (1975).
• 10: W. Feller, An Introduction to Probability Theory and its Applications,Vol. I, Third Edition, John Wiley and Sons, Inc., New York (1968).
• 11: G.R. Grimmett and C.J.H. McDiarmid, On colouring random graphs, Math.Proc.Camb. Phil.Soc. 77. 313-324 (1975).
• 12: R.M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R.E. Miller and J.W.Thatcher, eds., Plenum Press, New York, 85-104 (1972).
• 13: R.M. Karp, The probabilistic analysis of some combinatorial search algorithms, in Algorithms and Complexity, J.F. Traub, ed., Academic Press, New York (1976).
• 14: J. Komlós and E. Szemerédi, private communication.
• 15: G. Lev, Reversible concatenable lists, manuscript, Univ. of Edinburgh, Dept. of Comp. Sci.
• 16: L.A. Levin, Universal combinatorial problems (Russian), Problemi Peredaci Informacii, Vol. IX, 115-116 (1973).
• 17: L. Pósa, Hamiltonian circuits in random graphs, Discrete Mathematics 14, 359-364 (1976).
• 18: M.O. Rabin, Probabilistic algorithms, in Algorithms and Complexity, J.F. Traub, ed., Academic Press, New York, (1976).
• 19: C.P. Schnorr, Optimal algorithms for self-reducible problems, Proc. Third International Colloquium on Automata, Languages and Programming, S. Michaelson and R. Milner, eds., Edinburgh University Press, 322-337 (1976).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Theory