Maximum cardinality matchings on trees by randomized local search

ABSTRACT

To understand the working principles of randomized search heuristics like evolutionary algorithms they are analyzed on optimization problems whose structure is well-studied. The idea is to investigate when it is possible to simulate clever optimization techniques for combinatorial optimization problems by random search. The maximum matching problem is well suited for this approach since long augmenting paths do not allow immediate improvements by local changes. It is known that randomized search heuristics like simulated annealing, the Metropolis algorithm, the (1+1) EA and randomized local search efficiently approximate maximum matchings for any graph; however, there are graphs where they fail to find maximum matchings in polynomial time. In this paper, we examine randomized local search (RLS) for graphs whose structure is simple. We show that RLS finds maximum matchings on trees in expected polynomial time.

REFERENCES

• 1: C. Berge. Two theorems in graph theory. Proceedings of the National Academy of Sciences of the United States of America, 43:842--844, 1957.
• 2: P. Briest, D. Brockhoff, B. Degener, M. Englert, C. Gunia, O. Heering, T. Jansen, M. Leifhelm, K. Plociennik, H. Röglin, A. Schweer, D. Sudholt, S. Tannenbaum, and I. Wegener. Experimental supplements to the theoretical analysis of EAs on problems from combinatorial optimization. In Proceedings of the 8th Conference on Parallel Problem Solving from Nature (PPSN '04), volume 3242 of Lecture Notes in Computer Science, pages 21--30. Springer, 2004.
• 3: J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449--467, 1965.
• 4: Oliver Giel , Ingo Wegener, Evolutionary Algorithms and the Maximum Matching Problem, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.415-426, February 27-March 01, 2003
• 5: Jun He , Xin Yao, Time complexity analysis of an evolutionary algorithm for finding nearly maximum cardinality matching, Journal of Computer Science and Technology, v.19 n.4, p.450-458, July 2004 [doi>10.1007/BF02944746]
• 6: J. E. Hopcroft and R. M. Karp. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225--231, 1973.
• 7: M. Jerrum. Large cliques elude the Metropolis process. Random Structures and Algorithms, 3(4):347--359, 1992.
• 8: Mark Jerrum , Gregory B. Sorkin, The metropolis algorithm for graph bisection, Discrete Applied Mathematics, v.82 n.1-3, p.155-175, March 2, 1998 [doi>10.1016/S0166-218X(97)00133-9]
• 9: S. Micali and V. V. Vazirani. An O(√|V| ⋅ |E|) algorithm for finding maximum matching in general graphs. In Proceedings of the 21st Annual Symposium on Foundations of Computer Science (FOCS '80), pages 17--27. IEEE, 1980.
• 10: F. Neumann and I. Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. In Proceedings of the 6th Genetic and Evolutionary Computation Conference (GECCO '04), volume 3102 of LNCS, pages 713--724. Springer, 2004.
• 11: Galen Sasaki, The effect of the density of states on the Metropolis algorithm, Information Processing Letters, v.37 n.3, p.159-163, Feb. 18, 1991 [doi>10.1016/0020-0190(91)90037-I]
• 12: Galen H. Sasaki , Bruce Hajek, The time complexity of maximum matching by simulated annealing, Journal of the ACM (JACM), v.35 n.2, p.387-403, April 1988 [doi>10.1145/42282.46160]
• 13: Jens Scharnow , Karsten Tinnefeld , Ingo Wegener, Fitness Landscapes Based on Sorting and Shortest Paths Problems, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.54-63, September 07-11, 2002
• 14: V. V. Vazirani. A theory of alternating paths and blossoms for proving correctness of the O(√V E) maximum matching algorithm. Combinatorica, 14:71--109, 1994.
• 15: I. Wegener. Simulated annealing beats Metropolis in combinatorial optimization. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP '05), volume 3580 of LNCS, pages 589--601, 2005.
• 16: C. Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS '05), volume 3404 of LNCS, pages 44--56. Springer, 2005.

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

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

General Terms:
Algorithms, Theory

Keywords:
evolutionary algorithms, maximum cardinality matchings, randomized local search, runtime analysis