Fixed-parameter evolutionary algorithms and the vertex cover problem

ABSTRACT

In this paper, we consider multi-objective evolutionary algorithms for the Vertex Cover problem in the context of parameterized complexity. We relate the runtime of our algorithms to the input size and the cost of a minimum solution and point out that the search process of evolutionary algorithms creates partial solutions that are similar to the effect of a kernelization (i.e. a special type of preprocessing from parameterized complexity). Based on this, we show that evolutionary algorithms solve the vertex cover problem efficiently if the size of a minimum vertex cover is not too large, i.e. the expected runtime is bounded by O(f(OPT) n^c), where c is a constant and f a function that only depends on OPT. This shows that evolutionary algorithms are randomized fixed-parameter tractable algorithms for the vertex cover problem.

REFERENCES

• 1: M. L. Balinski. On maximum matching, minimum covering and their connections. In Proceedings of the Princeton symposium on mathematical programming, pages 434--445, 1970.
• 2: Jianer Chen , Iyad A. Kanj , Weijia Jia, Vertex cover: further observations and further improvements, Journal of Algorithms, v.41 n.2, p.280-301, November 2001 [doi>10.1006/jagm.2001.1186]
• 3: J. Chen, I. A. Kanj, and G. Xia. Improved parameterized upper bounds for vertex cover. In R. Kralovic and P. Urzyczyn, editors, MFCS, volume 4162 of LNCS, pages 238--249. Springer, 2006.
• 4: Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Introduction to Algorithms, Third Edition, The MIT Press, 2009
• 5: Benjamin Doerr , Edda Happ , Christian Klein, Crossover can provably be useful in evolutionary computation, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389202]
• 6: R. G. Downey and M. R. Fellows. Parameterized Complexity (Monographs in Computer Science). Springer, November 1998.
• 7: Vitaly Feldman, Evolvability from learning algorithms, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374465]
• 8: J. Flum , M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 9: Tobias Friedrich , Jun He , Nils Hebbinghaus , Frank Neumann , Carsten Witt, Analyses of simple hybrid algorithms for the vertex cover problem*, Evolutionary Computation, v.17 n.1, p.3-19, Spring 2009 [doi>10.1162/evco.2009.17.1.3]
• 10: Tobias Friedrich , Nils Hebbinghaus , Frank Neumann , Jun He , Carsten Witt, Approximating covering problems by randomized search heuristics using multi-objective models, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277118]
• 11: 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
• 12: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 13: G. L. Nemhauser and L. E. Trotter. Vertex packings: Structural properties and algorithms. Mathematical Programming, 8:232--248, 1975.
• 14: F. Neumann. Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem. European Journal of Operational Research, 181(3):1620--1629, 2007.
• 15: Frank Neumann , Ingo Wegener, Randomized local search, evolutionary algorithms, and the minimum spanning tree problem, Theoretical Computer Science, v.378 n.1, p.32-40, June, 2007 [doi>10.1016/j.tcs.2006.11.002]
• 16: P. S. Oliveto, J. He, and X. Yao. Evolutionary algorithms and the vertex cover problem. In Proc. of CEC 2007, IEEE Press, pages 1870--1877, 2007.
• 17: P. S. Oliveto, J.He, and X.Yao. Analysis of population-based evolutionary algorithms for the vertex cover problem. In Proc. of CEC 2008, IEEE Press, pages 1563--1570, 2008.
• 18: J. Scharnow, K. Tinnefeld, and I. Wegener. The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithms, pages 349--366, 2004.
• 19: L. G. Valiant. Evolvability. In L. Kucera and A. Kucera, editors, MFCS, volume 4708 of Lecture Notes in Computer Science, pages 22--43. Springer, 2007. Journal version appears in the Journal of ACM.
• 20: I. Wegener. Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In R. Sarker, X. Yao, and M. Mohammadian, editors, Evolutionary Optimization, pages 349--369. Kluwer, 2002.
• 21: C. Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Proc. of STACS 2005, volume 3404 of LNCS, pages 44--56, 2005.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Performance, Theory

Keywords:
combinatorial optimization, evolutionary algorithms, multi-objective optimization, runtime analysis