Evolving Solutions to Graph Theory Problems

Abstract

Randomized search heuristics such as evolutionary algorithms are general-purposetechniques that have been shown to be effective at solving combinatorial optimiza-tion problems. In this thesis, we use both empirical and theoretical techniques toexamine the use of a simple evolutionary algorithm, the (1+1) EA, applied to com-binatorial optimization problems from graph theory. First, we investigate the evo-lutionary algorithm on problemsk-VertexCover,k-FeedbackVertexSet, andk-OddCycleTransversal, and present Fixed-Parameter Tractable performanceguarantees for the (1+1) EA equipped with a tailored jump-and-repair operator. Wethen follow up with empirical results of the (1+1) EA applied to thek-VertexCoverproblem. Next we move on to investigate the (1+1) EA applied to graceful labeling.We present the first rigorous runtime analysis of an evolutionary algorithm findinggraceful labelings of graphs, and prove polynomial time upper bounds for paths, stars,and complete bipartite graphs with a constant sized partition. To supplement thetheoretical results, we also empirically compare the performance of the (1+1) EA tothat of a complete constraint solver.ii