Two-phase heuristics for the k-club problem

Given an undirected graph G and an integer k, a k-club is a subset of nodes that induces a subgraph with diameter at most k. The k-club problem consists of identifying a maximum cardinality k-club in G. It is an NP-hard problem. The problem of checking if a given k-club is maximal or if it is a subset of a larger k-club is also NP-hard, due to the non-hereditary nature of the k-club structure. This non-hereditary nature is adverse for heuristic strategies that rely on single-element add and delete operations. In this work we propose two-phase algorithms which combine simple construction schemes with exact optimization of restricted integer models to generate near optimal solutions for the k-club problem. Numerical experiments on sets of uniform random graphs with edge densities known to be very challenging and test instances available in the literature indicate that the new algorithms are quite effective, both in terms of solution quality and running times.