Analysis of Iterated Greedy Heuristic for Vertex Clique Covering


  • David Chalupa Operations Research Group, Department of Materials and Production Aalborg University, Aalborg 9220
  • Jiří Pospíchal Faculty of Natural Sciences, University of SS. Cyril and Methodius, 917 01 Trnava


Vertex clique covering problem, iterated greedy, randomised search heuristics, complex networks, random graphs


The aim of the vertex clique covering problem (CCP) is to cover the vertices of a graph with as few cliques as possible. We analyse the iterated greedy (IG) algorithm for CCP, which was previously shown to provide strong empirical results for real-world networks. It is demonstrated how the techniques of analysis for randomised search heuristics can be applied to IG, and several practically relevant results are obtained. We show that for triangle-free graphs, IG solves CCP optimally in expected polynomial time. Secondly, we show that IG finds the optimum for CCP in a specific case of sparse random graphs in expected polynomial time with high probability. For Barabási-Albert model of scale-free networks, which is a canonical model explaining the growth of social, biological or computer networks, we obtain that IG obtains an asymptotically optimal approximation in polynomial time in expectation. Last but not least, we propose a slightly modified variant of IG, which guarantees expected polynomial-time convergence to the optimum for graphs with non-overlapping triangles.


Download data is not yet available.




How to Cite

Chalupa, D., & Pospíchal, J. (2018). Analysis of Iterated Greedy Heuristic for Vertex Clique Covering. COMPUTING AND INFORMATICS, 37(2), 385–404. Retrieved from