A decomposition branch-and-cut algorithm for the maximum cross-graph $k$-club problem


The analysis of social and biological networks often involves modeling clusters of interest as cliques or their graph-theoretic generalizations. The $k$-club model, which relaxes the requirement of pairwise adjacency in a clique to length-bounded paths inside the cluster, has been used to model cohesive subgroups in social networks and functional modules/complexes in biological networks. However, if the graphs are time-varying, or if they change under different conditions, we may be interested in clusters that preserve their property over time or under changes in conditions. To model such clusters that are conserved in a collection of graphs, we consider a cross-graph $k$-club model, a subset of nodes that forms a $k$-club in every graph in the collection. In this paper, we consider the canonical optimization problem of finding a cross-graph $k$-club of maximum cardinality. We introduce algorithmic ideas to solve this problem and evaluate their performance on some benchmark instances.