A ‐club is a distance‐based graph‐theoretic generalization of a clique, originally introduced to model cohesive social subgroups in social network analysis. The ‐clubs represent low diameter clusters in graphs and are appropriate for various graph‐based data mining applications. Unlike cliques, the ‐club model is nonhereditary, meaning every subset of a ‐club is not necessarily a ‐club. In this article, we settle an open problem establishing the intractability of testing inclusion‐wise maximality of ‐clubs. This result is in contrast to polynomial‐time verifiability of maximal cliques, and is a direct consequence of its nonhereditary nature. We also identify a class of graphs for which this problem is polynomial‐time solvable. We propose a distance coloring based upper‐bounding scheme and a bounded enumeration based lower‐bounding routine and employ them in a combinatorial branch‐and‐bound algorithm for finding maximum cardinality ‐clubs. Computational results from using the proposed algorithms on 200‐vertex graphs are also provided.
