University of Hull logo

Analysis of an iterated greedy heuristic for vertex clique covering

Chalupa, David; Pospíchal, Jiří

Authors

David Chalupa

Jiří Pospíchal

Abstract

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 Baraba´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.

Journal Article Type Article
Publication Date Apr 30, 2018
Journal Computing and informatics
Print ISSN 1335-9150
Electronic ISSN 2585-8807
Peer Reviewed Peer Reviewed
Volume 37
Issue 2
Article Number 385-404
Pages 385-404
Institution Citation Chalupa, D., & Pospíchal, J. (2018). Analysis of an iterated greedy heuristic for vertex clique covering. Computing and Informatics, 37(2), 385-404. https://doi.org/10.4149/cai_2018_2_385
DOI https://doi.org/10.4149/cai_2018_2_385
Keywords Vertex clique covering problem; Iterated greedy; Randomised search heuristics; Complex networks; Random graphs
Publisher URL http://www.cai.sk/ojs/index.php/cai/article/view/2018_2_385
Copyright Statement ©2018 University of Hull
Additional Information This is the accepted manuscript of an article published in Computing and informatics, 2018. The version of record is available at the DOI link in this record.

Files




Downloadable Citations