‘A dynamic programming algorithm for the maximum $s$-club problem on trees’
Authors: José Alberto Fernández-Zepeda, Alejandro Flores-Lamas, Matthew Hague, Joel Antonio Trejo-Sánchez.
Abstract
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 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 \cdot 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.
Keywords: Maximum $s$-club, Clique relaxations, Dynamic programming, Tree graphs, Graph algorithms
- A dynamic programming algorithm for the maximum $s$-club problem on trees:
- License
- European Journal of Operational Research.