Approximating vertex cover using edge-based representations

In the literature only lower bounds are available on the approximation ratio of randomised search heuristics for vertex cover in the single-objective problem setting. These analyses are based on the natural vertex-based representation. Inspired by a well-known problem-specific approximation algorithm, we present an analysis of randomised search heuristics using edge-based representations. For the canonical objective function we prove that the performance can still be arbitrarily bad for the (1+1) EA and also RLS, even when using large search neighbourhoods. Adding slightly more information to the objective function turns RLS and the (1+1) EA into efficient 2-approximation algorithms requiring O(mlogm) steps where m is the number of edges. Although equivalent in the worst case, such an upper bound on the runtime is at least a linear factor better than that of the multi-objective case for sparse graphs and for graphs with large optimal vertex covers. Furthermore RLS algorithms, that after an improvement do not flip tested bits before trying previously untested ones, guarantee 2-approximations in O(m) steps.