The Maximum Ratio Clique Problem: A Continuous Optimization Approach and Some New Results

In this paper, we are interested in studying the maximum ratio clique problem (MRCP) that is a variant of the classical maximum weight clique problem. For a given graph, we suppose that each vertex of the graph is weighted by a pair of rational numbers. The objective of MRCP consists in finding a maximal clique with the largest ratio between two sets of weights that are assigned to its vertices. It has been proven that the decision version of this problem is NP-complete and it is hard to solve MRCP for large instances. Hence, this paper looks for introducing an efficient approach based on Difference of Convex functions (DC) programming and DC Algorithm (DCA) for solving MRCP. Then, we verify the performance of the proposed method. For this purpose, we compare the solutions of DCA with the previously published results. As a second objective of this paper, we identify some valid inequalities and evaluate empirically their influence in solving MRCP. According to the numerical experiments, DCA provides promising and competitive results. Furthermore, the introduction of the valid inequalities improves the computational time of the classical approaches.