Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs

In this paper, we relate the problem of finding a maximum clique to the intersection number of the input graph (i.e. the minimum number of cliques needed to edge cover the graph). In particular, we consider the maximum clique problem for graphs with small intersection number and random intersection graphs (a model in which each one of

m

labels is chosen independently with probability

p

by each one of

n

vertices, and there are edges between any vertices with overlaps in the labels chosen).

We first present a simple algorithm which, on input

G

finds a maximum clique in

$O(2^{2^m + O(m)} + n^2 \min\{2^m, n\})$

time steps, where

m

is an upper bound on the intersection number and

n

is the number of vertices. Consequently, when

m

 ≤ ln ln

n

the running time of this algorithm is polynomial.

We then consider random instances of the random intersection graphs model as input graphs. As our main contribution, we prove that, when the number of labels is not too large (

m

 = 

n

α

, 0 < 

α

 < 1), we can use the label choices of the vertices to find a maximum clique in polynomial time whp. The proof of correctness for this algorithm relies on our Single Label Clique Theorem, which roughly states that whp a “large enough” clique cannot be formed by more than one label. This theorem generalizes and strengthens other related results in the state of the art, but also broadens the range of values considered (see e.g. [22] and [4]).

As an important consequence of our Single Label Clique Theorem, we prove that the problem of inferring the complete information of label choices for each vertex from the resulting random intersection graph (i.e. the

label representation of the graph

) is

solvable

whp; namely, the maximum likelihood estimation method will provide a unique solution (up to permutations of the labels). Finding efficient algorithms for constructing such a label representation is left as an interesting open problem for future research.