# Multivariate Algorithmics for Finding Cohesive Subnetworks
## 2 Degree-Based Clique Relaxations
### Absolute Relaxation of the Maximum Degree: \(s\)-Plexes  
A natural idea is to relax the clique definition by allowing for each vertex of \(S\) a fixed number of non-neighbors in \(S\). **Definition 5**. : A set \(S\subseteq V\) is an \(s\)-_plex_ in a graph \(G=(V,E)\) if every vertex in \(G[S]\) has degree at least \(|S|-s\). This clique relaxation was introduced by [PERSON] and [PERSON] [26]. An equivalent definition is that a set \(S\) is an \(s\)-plex if and only if every set of \(s\) vertices of \(S\) is a dominating set in \(G[S]\)[26]. Figure 2 shows the maximum-cardinality \(3\)-plex in the highland tribes example. This \(3\)-plex is a proper superset of the maximum clique, and thus, it represents a cohesive group with additional members (that would be missing from an analysis solely based on the clique definition). The property of being an \(s\)-plex is hereditary: deleting a vertex \(v\) from an \(s\)-plex may reduce the degree of every other vertex by at most one; at the same time, it decreases the number of vertices by one. The structural properties of \(s\)-plexes are influenced by the relation between the size \(k\) of an \(s\)-plex and \(s\). For example, every graph of order at most \(s+1\) is an \(s\)-plex. In contrast, if \(s<k/2+1\), then \(G[S]\) has diameter two [26]. This is of course a desirable property for cohesive groups. As for Clique, we are interested in the problem of finding large \(s\)-plexes. * \(s\)-Plex
* An undirected graph \(G\) and an integer \(k\). * Does \(G\) contain an \(s\)-plex \(S\) of size at least \(k\)?Since the \(s\)-plex property is hereditary, Theorem 1 implies that \(s\)-Plex is NP-hard. Let us thus inspect the multivariate complexity picture for \(s\)-Plex. The first, obvious, parameter to consider is the solution size \(k\). Here, fixed-parameter algorithms are unlikely: for every fixed \(s\), \(s\)-Plex is W[1]-hard for the parameter \(k\). This follows from Theorem 2 and from a simple parameterized reduction from Clique[27]. This reduction reduces Clique instances in which we search for a clique of size at least \(k\) to \(s\)-Plex instances in which we search for an \(s\)-plex of size at least \(s\cdot k\). Thus, for every constant \(s\), an \(n^{o(k)}\)-time algorithm for \(s\)-Plex implies an \(n^{o(k)}\)-time algorithm for Clique, which violates the ETH. Summarizing, as for Clique, we cannot really exploit the solution size parameter, and one should search for different parameters or parameter combinations. Fortunately, positive results can be obtained for the dual parameter \(\ell:=n-k\) by generalizing the reduction of Clique to Vertex Cover described in Section 1.2. For Clique, the observation is that every clique is an independent set in the complement graph. Similarly, an \(s\)-plex has bounded degree in the complement graph: a vertex set \(S\) is an \(s\)-plex in \(G\) if and only if \(\hat{G}[S]\) has maximum degree at most \(s-1\). Thus, after transforming the input graph \(G\) to its complement graph \(\hat{G}\), we have to determine whether we can delete at most \(\ell\) vertices in \(\hat{G}\) to obtain a graph with maximum degree at most \(s-1\). This can be easily determined in \((s+1)^{\ell}\cdot n^{O(1)}\) time by a search tree algorithm that explores all possibilities to destroy subgraphs containing a vertex of degree at least \(s\)[27]. This algorithm is a fixed-parameter algorithm for the combined parameter \((s,\ell)\). Improving this to an \(f(\ell)\cdot n^{O(1)}\)-time algorithm, that is, to a fixed-parameter algorithm only for the parameter \(\ell\), is unlikely: \(s\)-Plex is W[2]-hard for the parameter \(\ell\) if \(s\) is part of the input [28]. The usefulness of the fixed-parameter algorithms based on the combined parameter \((s,\ell)\) was also confirmed experimentally for \(s=2\) and \(s=3\)[29]. Other approaches based on branch and cut [30] and on combinatorial algorithms [31] have roughly comparable performance.