Parsimonious formulations for low-diameter clusters

In the analysis of networks, one often searches for tightly knit clusters. One property of a ``good'' cluster is a small diameter (say, bounded by $k$), which leads to the concept of a $k$-club. In this paper, we propose new path-like and cut-like integer programming formulations for detecting these low-diameter subgraphs. They simplify, generalize, and/or dominate several previously existing formulations. Our best-performing formulation uses only node variables (quite unlike previous formulations) and imposes the diameter-at-most-$k$ constraints via an exponentially large class of cut-like inequalities. A relatively simple implementation of the cut-like formulation easily outperforms previous approaches, solving dozens of instances of the maximum $k$-club problem in a second or two that would take hours by other formulations. Moreover, the cut-like formulation is more general in the sense that it applies even when distances are not measured in terms of hops. While we consider only the $k$-club problem in this paper, the proposed techniques may also be useful in other applications where compact solutions are key (e.g., political districting and wildlife reserve design).

Citation

Submitted to a journal. Code is available at https://github.com/halisalemi/ParsimoniousKClub

Article

Download

View Parsimonious formulations for low-diameter clusters