Analysis of the Malatya Centrality-Based Clique Method on DIMACS Benchmarks and Random Graphs

The Maximum Clique Problem (MCP) is an NP-complete problem that aims to find the largest clique (complete subgraph) within a given graph. This problem has widespread applications in fields such as social network analysis, bioinformatics, chemical information systems, and communication networks. Although various solution methods have been proposed in the literature, an effective method that provides a general solution across different graph types is not yet available. In this study, we demonstrate that our previously proposed maximum clique method provides an effective solution for MCP on DIMACS benchmark graphs and random graphs generated using different models such as Erdos-Renyi, Forest Fire, Watts-Strogatz, and Regular Random models. The proposed method begins by computing the complement of the original graph. In the complement graph, the maximum independent set is determined using the Malatya Independent Set Algorithm, an efficient algorithm well-recognized in the literature. The maximum independent set identified in the complement graph is then used to determine the subgraph corresponding to the maximum clique in the original graph. The effectiveness of the proposed method was validated through tests on widely recognized DIMACS benchmark graphs. Additionally, to evaluate its performance and robustness on unpredictable graphs, tests were conducted on random graphs of varying complexities generated using Erdos-Renyi, Forest Fire, Watts-Strogatz, and Regular Random models. The results of these tests demonstrated that the method produced optimal or near-optimal MCP solutions for both DIMACS and random graphs. The successful outcomes further highlight the efficiency of the proposed method and its potential applicability in MCP-related domains.