# Multivariate Algorithmics for Finding Cohesive Subnetworks
## 2 Degree-Based Clique Relaxations
### Absolute Relaxation of the Maximum Degree: \(s\)-Plexes
The current-best algorithm for \(s\)-Plex is also based on a combinatorial search tree algorithm, which exploits that the \(s\)-plex property is hereditary [32]. Degree-based parameterizations of \(s\)-Plex have not been considered so far. For the parameter maximum degree \(\Delta\) of \(G\), a fixed-parameter algorithm can be easily obtained when \(s\) is also part of the parameter. First, the range of interesting values of \(k\) is bounded in \(\Delta+s\). **Observation 1**. : Any \(s\)-plex in a graph with maximum degree \(\Delta\) has size at most \(\Delta+s\). Consequently, instances where \(k>\Delta+s\) can be rejected immediately. Afterwards, any algorithm running in \(f(\Delta,k)\cdot n^{O(1)}\) time is also a fixed-parameter algorithm for the parameter \((\Delta,s)\). If we are interested only in connected \(s\)-plexes, then Proposition 1 can be directly applied. Otherwise, the algorithm is more complicated, but by applying a generic algorithm [14] (Theorem 4), one obtains a \(\Delta^{O(\Delta+s)}\cdot n\)-time algorithm for \(s\)-Plex. (To check that [14] (Theorem 4) applies to \(s\)-Plex, it is  
Figure 2: A part of the highland tribes social network [4]. The black vertices form the maximum 3-plex and the maximum 0.6-complete set in this network. sufficient to formulate \(s\)-Plex as an optimization problem satisfying certain criteria. We omit the straightforward proof.) **Proposition 2**. : \(s\)-Plex _is fixed-parameter tractable with respect to the parameter \((\Delta,s)\)._  
There are two ways of improving this observation. Obviously, one should try to improve the running time. For example, is a running time of \(2^{O(\Delta+s)}\cdot n^{O(1)}\) possible? Maybe it would be more relevant in applications to improve the parameterization, that is, to obtain fixed-parameter algorithms for the smaller parameters \(h\)-index of \(G\) or degeneracy of \(G\). Given the small value of the degeneracy \(d\) in practice, parameterization by \(d\) seems particularly promising. The following tractability result can be easily obtained. **Proposition 3**. : \(s\)-Plex _can be solved in \(2^{d}\cdot n^{O(s)}\) time._  
Proof. : Use the following algorithm. Pick a vertex \(v\) of \(G\) that has degree at most \(d\). Determine whether there is an \(s\)-plex \(S\) of order at least \(k\) containing \(v\) by trying all possibilities for \(S\cap N(v)\) (there are \(O(2^{d})\) many) and all possibilities for \(S\setminus N[v]\) (there are \(O(n^{s-1})\) many). For each combination, check in polynomial time whether it is an \(s\)-plex. If no \(s\)-plex has been found, then continue with \(G-v\). Thus, for constant \(s\), we achieve a fixed-parameter algorithm for the degeneracy parameter \(d\). Since \(n\) is very large in many applications, the \(n^{O(s)}\) term is, however, prohibitive in many practical settings already for \(s=3\). A more efficient algorithm running in \(f(d,s)\cdot n^{O(1)}\) time is thus highly desirable. **Open Question 1**. : Is \(s\)-Plex fixed-parameter tractable with respect to the parameter \((d,s)\) where \(d\) is the degeneracy of the input graph \(G\)? A positive answer to this question could provide a sizable step towards efficient fixed-parameter algorithms for many real-world instances of \(s\)-Plex.