Analysis of an iterated greedy heuristic for vertex clique covering

Chalupa, David; Pospíchal, Jiří

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.

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

• Journal Article Type: Article
• Acceptance Date: Sep 14, 2016
• Publication Date: Apr 30, 2018
• Deposit Date: Oct 25, 2016
• Publicly Available Date: May 1, 2019
• 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
• DOI: https://doi.org/10.4149/cai_2018_2_385
• Keywords: Vertex clique covering problem; Iterated greedy; Randomised search heuristics; Complex networks; Random graphs
• Public URL: https://hull-repository.worktribe.com/output/444539
• Publisher URL: http://www.cai.sk/ojs/index.php/cai/article/view/2018_2_385
• 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.
• Contract Date: Jan 3, 2018