  Finding large "cliquish" subgraphs is a central topic in graph mining and
community detection. A popular clique relaxation are 2-clubs: instead of asking
for subgraphs of diameter one (these are cliques), one asks for subgraphs of
diameter at most two (these are 2-clubs). A drawback of the 2-club model is
that it produces star-like hub-and-spoke structures as maximum-cardinality
solutions. Hence, we study 2-clubs with the additional constraint to be
well-connected. More specifically, we investigate the algorithmic complexity
for three variants of well-connected 2-clubs, all established in the
literature: robust, hereditary, and "connected" 2-clubs. Finding these more
cohesive 2-clubs is NP-hard; nevertheless, we develop an exact combinatorial
algorithm, extensively using efficient data reduction rules. Besides several
theoretical insights we provide a number of empirical results based on an
engineered implementation of our exact algorithm. In particular, the algorithm
significantly outperforms existing algorithms on almost all (sparse) real-world
graphs we considered.
