A dynamic programming algorithm for the maximum <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si265.svg" display="inline" id="d1e1139"> <mml:mi>s</mml:mi> </mml:math> -club problem on trees

Computing cliques in an undirected graph G = ( V G , E G ) is a fundamental problem in social network analysis. However, in some cases, the strict definition of a clique (a subset of vertices pairwise adjacent in G ) often limits its applicability in real-world settings. To address this issue, we study the s -club: a clique relaxation that induces a subgraph of diameter at most s . Note that a clique is simply a 1-club. Computing a maximum s -club is a computationally challenging problem, as it is NP-hard for any positive integer s in arbitrary graphs. Thus, this paper presents a simple dynamic programming algorithm that efficiently computes a maximum s -club on an n -vertex tree in O ( s ⋅ n ) time. This algorithm outperforms existing algorithms for trees in theory and practice. This approach is a stepping stone towards computing maximum s -clubs on tree-like graphs. • A simple dynamic programming approach to compute a maximum s -club on trees. • For an arbitrary n -vertex tree, the presented algorithm runs in O ( s ⋅ n ) time. • Experimental results (on real and synthetic trees) confirm the theoretical analysis.