Improved runtime analysis of RLS and (1+1) EA for the dynamic vertex cover problem

Abstract

In this paper, we perform theoretical analyses of the behaviour of an evolutionary algorithm and a randomised search algorithm on the dynamic vertex cover problem. The dynamic vertex cover problem has already been theoretically investigated for these two algorithms to some extent. We improve some of the existing results, i. e. we find a linear expected re-optimization time for a (1+1) EA to maintain a 2-approximation when edges are dynamically deleted from the graph. Furthermore, we investigate a different setting for the dynamic version of the problem, in which a dynamic change happens at each step with probability PD. We prove that when PD ≤ 1/(2+ϵ)em, where m is the number of edges of the graph, RLS and (1+1) EA find a 2-approximate solution from an arbitrary initial solution in expected time O(m log m). Furthermore, we prove that in expected time O(m) after the first dynamic change, they recompute a 2-approximate solution.