Home » Publication » 27520

Dettaglio pubblicazione

2023, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, Pages 1008-1025 (volume: 307)

CliSAT: A new exact algorithm for hard maximum clique problems (01a Articolo in rivista)

San Segundo P., Furini F., Alvarez D., Pardalos P. M.

Given a graph, the maximum clique problem (MCP) asks for determining a complete subgraph with the largest possible number of vertices. We propose a new exact algorithm, called CliSAT , to solve the MCP to proven optimality. This problem is of fundamental importance in graph theory and combinatorial optimization due to its practical relevance for a wide range of applications. The newly developed exact approach is a combinatorial branch-and-bound algorithm that exploits the state-of-the-art branching scheme enhanced by two new bounding techniques with the goal of reducing the branching tree. The first one is based on graph colouring procedures and partial maximum satisfiability problems arising in the branching scheme. The second one is a filtering phase based on constraint programming and domain propagation techniques. CliSAT is designed for structured MCP instances which are computationally difficult to solve since they are dense and contain many interconnected large cliques. Extensive experiments on hard benchmark instances, as well as new hard instances arising from different applications, show that CliSAT outperforms the state-of-the-art MCP algorithms, in some cases by several orders of magnitude.
Gruppo di ricerca: Combinatorial Optimization
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma