Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem

We contribute to the theoretical understanding of randomized search\nheuristics for dynamic problems. We consider the classical vertex coloring\nproblem on graphs and investigate the dynamic setting where edges are added to\nthe current graph. We then analyze the expected time for randomized search\nheuristics to recompute high quality solutions. The (1+1)~Evolutionary\nAlgorithm and RLS operate in a setting where the number of colors is bounded\nand we are minimizing the number of conflicts. Iterated local search algorithms\nuse an unbounded color palette and aim to use the smallest colors and,\nconsequently, the smallest number of colors.\n We identify classes of bipartite graphs where reoptimization is as hard as or\neven harder than optimization from scratch, i.e., starting with a random\ninitialization. Even adding a single edge can lead to hard symmetry problems.\nHowever, graph classes that are hard for one algorithm turn out to be easy for\nothers. In most cases our bounds show that reoptimization is faster than\noptimizing from scratch. We further show that tailoring mutation operators to\nparts of the graph where changes have occurred can significantly reduce the\nexpected reoptimization time. In most settings the expected reoptimization time\nfor such tailored algorithms is linear in the number of added edges. However,\ntailored algorithms cannot prevent exponential times in settings where the\noriginal algorithm is inefficient.\n