On atomic cliques in temporal graphs


Atomic cliques were introduced recently to analyze disease progression in temporal comorbidity graphs. Informally, an atomic clique is a clique that is unsplittable over time—the clique is either present or absent entirely and no parts of it appears in the temporal graph unless the entire clique is present. 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. The proposed approach is also applicable when solving variants like the minimum atomic clique partitioning problem or the maximum weighted atomic clique problem.

Optimization Letters, 17(4):813–828
Yajun Lu
Yajun Lu
Assistant Professor of Analytics & Operations Management

My research interests are in Network Optimization, Graph-based Data Mining, Data Analytics of Complex Networks with applications in Healthcare, and Social Network Analysis.