# Multivariate Algorithmics for Finding Cohesive Subnetworks
## Average \(s\)-Plex  
**Input:** An undirected graph \(G\) and an integer \(k\).  
**Question:** Does \(G\) contain an average \(s\)-plex \(S\) of size at least \(k\)?  
Since being an average \(s\)-plex is quasi-hereditary, it is sufficient to search for an average \(s\)-plex of size _exactly_\(k\). Hence, for every fixed \(k\), the problem is equivalent to \(\gamma\)-Quasi-Clique and, therefore, NP-hard; the only difference is that \(s\) and \(\gamma\) assume different values and, thus, present different possibilities for parameterization.  
An integer programming formulation for Average \(s\)-Plex was presented by [PERSON] _et al._[PERSON] _et al._ (2016), but the multivariate complexity of Average \(s\)-Plex has not been studied so far.  
**Open Topic 3.** Perform a multivariate complexity analysis of Average \(s\)-Plex.  
A first hardness result is easily obtained by exploiting the connection between average \(s\)-plexes and \(\gamma\)-quasi-cliques.  
**Proposition 8**: Average \(s\)-Plex _is W[1]-hard with respect to the combined parameter \((d,k,s)\)._  
We present a simple parameterized reduction from \(\gamma\)-Quasi-Clique. Let \((G,k)\) be an instance of \(\gamma\)-Quasi-Clique. Due to the quasi-hereditarity, this instance is a yes-instance if and only if \(G\) contains a \(\gamma\)-quasi-clique of order exactly \(k\). By Observation 5, this is the case if and only if \(G\) contains an average \(s\)-plex of size \(k\) where \(s=k-\gamma\cdot k+\gamma\leq k\). Thus, setting \(s\) to this value and leaving \(G\) and \(k\) unchanged gives a parameterized reduction from \(\gamma\)-Quasi-Clique parameterized by \((d,k)\) to average \(s\)-plex parameterized by \((d,k,s)\).  
As in the case of \(s\)-Plex, a fixed-parameter algorithm for Average \(s\)-Plex can be easily obtained for the parameter \((\Delta,s)\). First, we observe that the size of average \(s\)-plexes is bounded in \(\Delta+s\).  
Any average \(s\)-plex in a graph with maximum degree \(\Delta\) has size at most \(\Delta+s\).  
Thus, after rejecting instances where \(k\) is too big, any algorithm running in \(f(\Delta,k)\cdot n^{O(1)}\) time is also a fixed-parameter algorithm for the parameter \((\Delta,s)\). Such an algorithm can be obtained by a reduction to \(\gamma\)-Quasi-Clique that consists only of setting \(\gamma\) appropriately (observe that \(\gamma\) depends only on \(\Delta\) and \(s\)).  
**Proposition 9**: Average \(s\)-Plex _is fixed-parameter tractable with respect to \((\Delta,s)\)._  
For all of the parameters under consideration so far, the complexity of \(\gamma\)-Quasi-Clique and Average \(s\)-Plex are the same. Therefore, it is not clear whether or not the parameter \(s\) can be exploited by fixed-parameter algorithms at all. One candidate for positive results is to combine \(s\) with the dual parameter \(\ell\). Here, it is less obvious whether previous hardness results for \(\gamma\)-Quasi-Clique transfer.  
**Open Question 6.** Is Average \(s\)-Plex fixed-parameter tractable with respect to \((\ell,s)\)?  
This question is particularly interesting, because for the related \(s\)-Plex problem, parameterization by \((\ell,s)\) leads to practical fixed-parameter algorithms (K  
cliques are the only sets of size \(k\) assuming these connectivity values. Hence, vertex-connectivity and edge-connectivity can be used as clique-defining properties when related to the total number of vertices. Thus, clique relaxations can be obtained by relaxing them. In the following, let \(\kappa(G)\) denote the vertex-connectivity of a graph \(G\), and let \(\lambda(G)\) denote its edge-connectivity. Observe that \(\kappa(G)\leq\lambda(G)\leq\delta(G)\) where \(\delta(G)\) denotes the minimum degree in \(G\).