On atomic cliques in temporal graphs

Abstract

Atomic cliques were introduced recently to analyze comorbidity graphs that vary over time. We consider the atomic counterpart of the classical maximum clique problem in this paper. Our main contribution is a polynomial-time algorithm that transforms the maximum atomic clique problem to the maximum clique problem on an auxiliary graph. We report results from our computational studies that demonstrate the effectiveness of this transformation in solving the maximum atomic clique problem in comparison to direct integer programming based approaches.