An Improved Upper Bound on Maximal Clique Listing via Rectangular Fast Matrix Multiplication

The first output-sensitive algorithm for the Maximal Clique Listing problem was given by Tsukiyama et al. (SIAM J Comput 6(3):505–517, 1977). As any algorithm falling within the Reverse Search paradigm, it performs a DFS visit of a directed tree (the RS-tree) having the objects to be listed (i.e., maximal cliques) as its nodes. In a recursive implementation, the RS-tree corresponds to the recursion tree of the algorithm. The time delay is given by the cost of generating the next child of a node, and Tsukiyama et al. showed it is O(mn). Makino and Uno (in: Hagerup, Katajainen (eds) Algorithm theory: SWAT 2004. Lecture notes in computer science, Springer, Berlin, pp 260–272, 2004) sharpened the time delay to \(O(n^{\omega })\) by generating all the children of a node in one single shot, which is performed by computing a square fast matrix multiplication. In this paper we further improve the asymptotics for the exploration of the same RS-tree by grouping the offsprings’ computation even further. Our idea is to rely on rectangular fast matrix multiplication in order to compute all children of \(n^2\) nodes in one single shot. According to the current upper bounds on square and rectangular fast matrix multiplication, with this the time delay improves from \(O(n^{2.3728639})\) to \(O(n^{2.093362})\), keeping a polynomial work space.