On Exact Algorithms For The Maximum Clique Problem

Given a graph G =(V,E),a clique is a subgraph of G in which each pair of vertices are adjacent to each other.The Maximum Clique problem(MCP)consist in finding a clique with the largest number of vertices.An important generalization of MCP is the Maximum Weight Clique problem(MWCP),in which the graph has a weight function w that assigns a positive integer called weight to each vertex.MWCP is to find a clique of maximum weight.MCP(MWCP)is a relevant NP-hard problem with real-world applications in fields such as fault diagnosis,bioinformatics and chemoinformatics,coding theory,economics,and social network analysis.A huge amount of effort has been devoted to solve MCP(MWCP)and,as a result,there exist two main types of algorithms:heuristic and exact.Exact algorithms are usually based on the Branch-and-Bound(BnB)scheme and can grantee to find the optimal solutions.In this thesis,we focus on BnB algorithms for MCP and MWCP.Given a graph G=(V,E),the BnB algorithms for MCP are to find a clique of max-imum size in G by efficiently traversing the search space formed by all the proper subsets of the set of vertices V.The key point of efficiency is that how these algorithms reduce the search space.To this end,we proposed an approach based on MaxSAT reasoning,called incremental MaxSAT reasoning,to reduce the number of branching vertices.Concretely,at each node of the search space,and knowing that the largest clique found so far has size r,we partition V into a set A,such that the subgraph induced by A has a maximum clique of size not greater than the r,and a set B = V\A of branching vertices.Then,incremental MaxSAT reasoning successively inserts into A the vertex bi ? B,showing that the upper bound of a maximum clique in the subgraph induced by A is still not greater than r.Consequently,the branching set B is reduced,resulting in less search space.We implemented two strategies to reduce B:dynamic and static.The dynamic strategy minimizes B without any constraint,and induces a dynamic vertex ordering in G during the search,resulting in the algorithm called DoMC.The static strategy minimizes B subject to the constraint that a static vertex ordering in G must be kept during the search,resulting in two BnB algorithms called SoMC.We analyzed the two strategies and found that they are complementary.From this observation,we proposed a new algorithm,called MoMC,that combines the strengths of the two strategies into a single algorithm.The reported experimen-tal results show that,thanks to incremental MaxSAT reasoning,DoMC,SoMC and MoMC significantly outperform the state-of-the-art algorithms for MCP,and MoMC is generally better than the algorithms implementing a single strategy.Clique is a valuable property for analyzing real-world large graphs.We proposed a new exact algorithm,called LMC,to solve MCP in large graphs.LMC combines a novel preprocessing and incremental MaxSAT reasoning in a BnB scheme.The preprocessing procedure performs effectively three tasks simultaneously with a very low overhead:derive a vertex ordering,reduce the graph,and compute an initial clique.LMC shows a performance that is superior over two state-of-the-art exact algorithms:PMC and BBMCSP,and refutes the opinion in the literature that sophisticated techniques such as MaxSAT reasoning are not useful for large sparse graphs.We also proposed an efficient exact algorithm,called WLMC,for MWCP in large graphs.WLMC incorporates two original contributions:a preprocessing to derive an initial vertex ordering and to reduce the size of the graph,and conflict-driven vertex-weight Split-ting(CDWS)to reduce the number of branches in the search space.The empirical results show that WLMC greatly outperforms relevant heuristic and exact solvers on real-world large instances,and refute the prevailing hypothesis that exact algorithms are less adequate for large graphs.