Groupe d’études et de recherche en analyse des décisions

# An Exact Algorithm for the Maximum k-Club Problem in an Undirected Graph

## Jean-Marie Bourjolly, Gilbert Laporte et Gilles Pesant

In this paper, we prove that the maximum k-club problem defined on an undirected graph is NP-hard. We also give an integer programming formulation for this problem as well as an exact branch-and-bound algorithm and computational results on instances involving up to 200 vertices. Instances defined on very dense graphs can be solved to optimality within insignificant computing times. The most difficult cases appear to be those where the graph density is around 0.15.

, 13 pages