View on GitHub

maximum-s-club-set-on-trees.io

‘A dynamic programming algorithm for a maximum $s$-club set on trees’

Authors: José Alberto Fernández-Zepeda, Alejandro Flores-Lamas, Matthew Hague, Joel Antonio Trejo-Sánchez.

Abstract

Finding clubs 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 club (a complete subgraph of $G$) can be too restrictive to model some social concepts. To address this issue, we study a relaxed version of the club, known as the $s$-club. An $s$-club is a maximal subgraph of $G$ in which the distance in $G$ between any pair of vertices of the subgraph is less than or equal to some positive integer $s$ (where a club is simply a $1$-club). Finding the maximum $s$-club in a graph is a computationally challenging problem, as it is NP-hard for any $s$ in arbitrary graphs. To overcome this challenge, we present a simple dynamic programming algorithm that efficiently solves the maximum $s$-club problem on an $n$-vertex tree in $O(s \cdot n)$ time for $s \geq 2$. This algorithm outperforms existing algorithms in theory and practice. This approach is a stepping stone to finding a maximum $s$-club in less restrictive graphs.

Keywords: Distance $s$-club, Graph algorithms, Trees, Dynamic programming, $s$-club.