An instance-specific hardware algorithm for finding a maximum clique

This paper presents a hardware algorithm for finding a maximum clique of a given graph, and shows experimental results of the proposed algorithm running on an FPGA. The proposed algorithm is constructed according to a given instance of graph, and can find a maximum clique efficiently based on branch and bound search. The proposed algorithm is designed to be implemented on FPGAs, and realizes an efficient branch and bound search with parallel and pipeline processing. Experimental results showed that, compared with the software solver, the proposed algorithm produced a maximum clique in a very shorter running time even if the time for circuit synthesis and configuration of FPGA was taken into account.