# Multivariate Algorithmics for Finding Cohesive Subnetworks
## Average \(s\)-Plex
### Relative Relaxation of Edge-Connectivity  
Instead of relaxing vertex-connectivity, one may also relax edge-connectivity in a relative way.  
**Definition 12**.: A set \(S\subseteq V\) in a graph \(G=(V,E)\) is \(\gamma\)-relative-edge-connected if \(\lambda(G[S])\geq\gamma\cdot(|S|-1)\).  
As for \(\gamma\)-relative-vertex-connected sets, there is a relation to \(\gamma\)-complete sets and \(\gamma\)-quasi-cliques: any \(\gamma\)-relative-edge-connected set is \(\gamma\)-complete. For large values of \(\gamma\), there is an even stronger connection between edge-connectivity and \(\gamma\)-complete graphs.  
**Theorem 3** ([56]).: _Let \(G\) be a graph on \(n\) vertices and let \(\gamma\geq n/(2n-2)\). Then, a graph \(G\) has edge-connectivity \(\gamma\cdot(n-1)\) if and only if it is \(\gamma\)-complete._  
Hence, \(\gamma\)-relative-edge-connectedness and \(\gamma\)-completeness are essentially the same for all constant \(\gamma>1/2\).  
\(\gamma\)-Relative-Edge-Connected Subgraph  
**Input:** An undirected graph \(G=(V,E)\) and an integer \(k\).  
**Question:** Does \(G\) contain a \(\gamma\)-relative-edge-connected set of size at least \(k\)?  
To our knowledge, \(\gamma\)-Relative-Edge-Connected Subgraph has not been studied so far, and the only computational problem in this context that has received attention deals with the following graph property.  
**Definition 13**.: A graph \(G=(V,E)\) on \(n\) vertices is _highly connected_ if \(\lambda(G)>n/2\).  
The notion of highly connected subgraphs was introduced in the context of graph clustering [57].  
Highly Connected Subgraph  
**Input:** An undirected graph \(G=(V,E)\) and an integer \(k\).  
**Question:** Does \(G\) contain a highly connected subgraph of order \(k\)?  
Highly Connected Subgraph turns out to be quite hard from a computational point of view. Highly Connected Subgraph is NP-hard and W[1]-hard for the parameter \((d,k)\) and W[1]-hard for the parameter \(\ell\)[58]. The parameter \(\Delta\) has not been considered so far, but the fact that every highly connected graph on \(k\) vertices has minimum degree \(k/2\) or more implies that the problem is nontrivial only if \(k\leq 2\Delta\). Hence, once again, we may apply Proposition 1 to obtain a fixed-parameter algorithm with running time \(\Delta^{O(\Delta)}\cdot n^{O(1)}\) for \(\Delta\). The complexity with respect to the \(h\)-index of \(G\) is open.  
Theorem 3 shows that the most interesting set of problems to study here are those where the edge-connectivity is below \(n/2\). It would be particularly interesting to highlight situations in which the complexities of \(\gamma\)-Relative-Edge-Connected Subgraph with \(\gamma<1/2\) and those of Highly Connected Subgraph and \(\gamma\)-Complete Graph differ.  
**Open Topic 5**.: Perform a multivariate complexity analysis for \(\gamma\)-Relative-Edge-Connected Subgraph.  
By the same reasoning as for \(\gamma\)-relative-vertex-connected sets, we have that \(\gamma\)-relative-edge-connected sets have size \(O(\Delta)\) for fixed values of \(\gamma\). Thus, by Proposition 1, there is an algorithm that solves \(\gamma\)-Relative-Edge-Connected Subgraph in \(\Delta^{O(\Delta)}\cdot n^{O(1)}\) time. For the other parameters, the complexity is open.