# Multivariate Algorithmics for Finding Cohesive Subnetworks
## 3 Distance-Based Clique Relaxations
### Induced Subgraphs with a Small Diameter: \(s\)-Clubs  
Demanding that all vertices of the group are connected by short paths _within_ the group is equivalent to demanding that the graph induced by the group has a low diameter. **Definition 7**. : A set \(S\subseteq V\) is an \(s\)-_club_ in a graph \(G=(V,E)\) if \(G[S]\) has diameter at most \(s\). \(s\)-Club  
**Input:**: An undirected graph \(G\) and an integer \(k\). **Question:**: Does \(G\) contain an \(s\)-club of size at least \(k\)? The fact that the \(s\)-club property is not quasi-hereditary implies that asking for an \(s\)-club of size _exactly_\(k\) is not equivalent: a graph may contain no \(s\)-club of size exactly \(k\) even if it contains an \(s\)-club of size \(k+1\). For every \(s>1\), \(s\)-Club is NP-hard [38], even when the input graph has diameter \(s+1\)[39]. For \(s=1\), \(s\)-Club is equivalent to Clique and, thus, W[1]-hard with respect to the solution size \(k\). In contrast, \(s\)-Club is fixed-parameter tractable with respect to \(k\) for all \(s>1\)[40; 41; 42]. There are two possible routes to obtain a fixed-parameter algorithm. Both rely on the following observation, where \(N_{\delta}[v]\) denotes the set of vertices that have distance at most \(\delta\) to \(v\). **Observation 3**. : For every vertex \(v\), the set \(N_{\lfloor s/2\rfloor}[v]\) is an \(s\)-club. Hence, if \(|N_{\lfloor s/2\rfloor}[v]|\geq k\) for some vertex \(v\), then \(N_{\lfloor s/2\rfloor}[v]\) is a valid solution of the problem. Otherwise, one may search for a maximum-cardinality \(s\)-club by inspecting for each vertex \(v\) the graph \(G[N_{\delta}[v]]\): if \(v\) is contained in the maximum \(s\)-club \(S\), then \(S\subseteq N_{\delta}[v]\). Now, since \(|N_{\lfloor s/2\rfloor}[v]|\leq k\), the size of \(N_{\delta}[v]\) is \(O(k^{2})\) for even \(s\) and \(O(k^{3})\) for odd \(s\)[40; 41; 42]. Thus, finding the maximum-cardinality \(s\)-clubs in these \(n\) many sets, for example by a brute-force algorithm, gives a fixed-parameter algorithm for \(s\)-Club and the parameter \(k\). The second approach works for the variant of \(s\)-Club, where we ask to find an \(s\)-club of size _exactly_\(k\), and is based on a special case of Observation 3. More precisely, it exploits the fact that for every vertex \(v\), \(N[v]\) is a 2-club. Hence, any graph with maximum degree \(\Delta\) has an \(s\)-club of size \(\Delta+1\). As a consequence, \(s\)-Club is nontrivially posed only if \(k>\Delta+1\). In this case, enumerating all connected induced subgraphs on at most \(k\) vertices, which can be done in \((e\cdot(\Delta-1))^{k}\cdot n^{O(1)}\) time [14], is possible in \((ek)^{k}\cdot n^{O(1)}\) time. Since \(s\)-clubs are connected, all that remains to be done is to check the \(s\)-club property for each enumerated induced subgraph in polynomial time. It is open to improve the worst-case running time substantially or to show a running time lower bound. **Open Question 2**. : Is it possible to determine in \(2^{O(k)}\cdot n^{O(1)}\) time whether a graph \(G\) has an \(s\)-club of size exactly \(k\)? This question is open already for \(s=2\). Clearly, it would also be desirable to obtain good running time bounds for the definition of \(s\)-Club as stated above, where we aim to find an \(s\)-club of size _at least_\(k\). Figure 3: A part of the highland tribes social network [4]. The black vertices form a maximal 2-club. The maximum 2-club consists of [PERSON] and all of its neighbors. For the dual parameter \(\ell:=n-k\), an efficient fixed-parameter algorithm for \(s\)-Club is achievable [41]. This algorithm is based on the fact that if \(V\) is not an \(s\)-club, then there are two vertices \(u\) and \(v\) in \(G\) that have distance at least \(s+1\). One of these two vertices cannot belong to \(S\). Thus, one may search recursively for an \(s\)-club of size at least \(k\) in \(G-v\) and in \(G-u\). In both recursive calls, \(n\) decreases by one, and since \(k\) remains the same, \(\ell\) decreases by one, as well.