A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques

We study the family of problems of partitioning and covering a graph into/with a minimum number of relaxed cliques. Relaxed cliques are subset of vertices of a graph for which a clique-defining property is relaxed, e.g., the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices. These graph partitioning and covering problems have important applications in many areas such as social network analysis, biology, and disease spread prevention. We propose a unified framework based on branch-and-price techniques to compute optimal decompositions. For this purpose, new e ective pricing algorithms are developed and new branching schemes are invented. In extensive computational studies, we compare several algorithmic designs, e.g., structure-preserving versus dichotomous branching and their interplay with di erent pricing algorithms. The finally chosen setup for the branch-and-price produces results that demonstrate the e ectiveness of all components of the newly developed framework and the validity of our approach when applied to social network instances.