An analytical investigation of block-based mutation operators for order-based stochastic clique covering algorithms
David Chalupa · 2013
We analyze the properties of a recently proposed order-based representation of the NP-hard (vertex) clique covering problem (CCP). In this representation, a permutation of vertices is mapped to a clique covering using greedy clique covering (GCC) and the identified cliques are put into the permutation as blocks. Block-based mutation operators can be then used to improve the clique covering in a stochastic algorithm, which is referred to as iterated greedy (IG). In this paper, we analytically investigate how the block-based mutation operators influence the quality of the solution. We formulate a sufficient condition for an improvement by a block-based operator to occur. We apply it in a proof of polynomial-time convergence of a block-based algorithm on paths. We also discuss the behavior of the algorithm on complements of bipartite graphs, where it can have a spectrum of possible behavior, ranging from polynomial-time convergence to getting stuck in a suboptimal solution. Worst-case result is proven for a graph class, where the algorithm gets stuck in a suboptimal solution with an overwhelming probability.