In a previous post we introduced the maximum clique problem (MCP) and reported performance of the efficient bit-parallel exact solver BBMC, implemented with BITSCAN and GRAPH libraries available in the Biicode repositories pablodev/bitscan and pablodev/graph respectively. BBMC is concerned with small and middle size graphs.

Also very challenging are real networks that arise from different fields such as social networks, infrastructure networks, scientific networks and so on. These graphs tend to have many thousands—even millions— of nodes but are usually very sparse —the Network Data Repository hosts more than 500 of such graphs—. An open problem is finding the clique number (the cardinality of a maximum clique) of such networks to get an insight into their structure. Unfortunately the problem is NP-hard and no polynomial algorithm is expected to be found; tailoring and exact solver for this task is as yet an open question [1].