Finding Hamilton cycles in random intersection graphs

The construction of the random intersection graph model is based on a random family of sets. Such structures, which are derived from intersections of sets, appear in a natural manner in many applications. In this article we study the problem of finding a Hamilton cycle in a random intersection graph. To this end we analyse a classical algorithm for finding Hamilton cycles in random graphs (algorithm HAM) and study its efficiency on graphs from a family of random intersection graphs (denoted here by G (n, m, p)). We prove that the threshold function for the property of HAM constructing a Hamilton cycle in G (n, m, p) is the same as the threshold function for the minimum degree at least two. Until now, known algorithms for finding Hamilton cycles in G (n, m, p) were designed to work in very small ranges of parameters and, unlike HAM, used the structure of the family of random sets.