A r-uniform hypergraph is like a graph, but edges are defined as being sets of r nodes. I.e., a graph is a 2-uniform hypergraph.

Say H is an r-uniform hypergraph on n vertices.

A clique in H is a set of vertices, say C, |C| = k, such that all choose(k, r) r-element subsets of the vertices of C are edges of H.

• Note that every (r-1) element subset of vertices is a trivial clique.
• A clique is said to be maximal if no larger clique contains it.

Given a particular r-uniform hypergraph H on n vertices, how can we efficiently count the maximal cliques of H (inclusive of trivial maximal cliques).

My current approach is exhaustive search. I begin with the set of all choose(n, r-1) trivial cliques. Then, for r <= s <= n, I check every s-element subset of V(H) to see if it’s a clique. If it is, I add it to my set of cliques, and remove all contained subcliques that haven’t already been removed (up to s = choose(s, s-1) of these). I represent both edges and cliques as bitvectors where the i’th bit being set means node i is present in the edge or clique.