# Multivariate Algorithmics for Finding Cohesive Subnetworks
## 2 Degree-Based Clique Relaxations
### Relative Relaxation of the Maximum Degree: \(\gamma\)-Complete Graphs  
In \(s\)-plexes, we relax the degree condition of cliques by an absolute amount of \(s-1\). It is just as natural to specify the amount of relaxation in a relative way, that is, to demand that each vertex of the set is adjacent to a large fraction of the set.  
**Definition 6**.: A vertex set \(S\) is \(\gamma\)_-complete_, \(0\leq\gamma\leq 1\), if every vertex in \(G[S]\) has degree at least \(\gamma\cdot(|S|-1)\). The graph \(G[S]\) is called a \(\gamma\)_-complete graph_.  
The model of \(\gamma\)-complete graphs was introduced several times [33; 34]. Sometimes, \(\gamma\)-complete graphs are also referred to as \(\gamma\)-quasi-cliques [35], but the term quasi-clique is more common in density-based clique relaxations (see Section 4). The 3-plex shown in Figure 2 is also a maximum 0.6-complete set in this network. In contrast to \(s\)-plexes, the property of being \(\gamma\)-complete is not hereditary. Removing for example \"Gahuk\" from the group gives a 0.5-complete set that is _not_ 0.6-complete. Moreover, the \(\gamma\)-completeness property is not even quasi-hereditary: Consider a cycle on five vertices. This graph is 0.5-complete. Deleting any vertex in this graph gives a path on four vertices. This graph is not 0.5-complete, as its degree-one vertices have too low a degree. If we consider only sets of a fixed size \(k\), then there is a direct correspondence between \(\gamma\)-complete sets and \(s\)-plexes: setting \(s\) to the largest integer such that \(k-s\geq\gamma(k-1)\), makes the definitions equivalent.  
When applying \(\gamma\)-complete sets in community detection, we have to solve the following problem.  
\(\gamma\)-Complete Graph  
**Input:** An undirected graph \(G\) and an integer \(k\).  
**Question:**: Does \(G\) contain a \(\gamma\)-complete set \(S\) of size at least \(k\)?  
Quite surprisingly, \(\gamma\)-Complete Graph has received much less attention than \(s\)-Plex. Since \(\gamma\)-completeness is not hereditary, Theorem 1 does not apply. From a complexity-theoretic perspective, it is known that \(\gamma\)-Complete Graph is NP-hard for \(\gamma=0.5\)[33]. A study of the complexity of \(\gamma\)-Complete Graph for all possible values of \(\gamma\) is clearly desirable. Moreover, a multivariate complexity analysis is also lacking. This leads us to the first open topic.  
**Open Topic 1.**: Perform a multivariate complexity analysis for \(\gamma\)-Complete Graph for all values of \(\gamma\).  
Similar to the case of \(s\)-Plex, the first tractability result for the parameter maximum degree \(\Delta\) can be obtained by observing that for fixed \(\gamma\), \(\gamma\)-complete sets cannot be too large compared to \(\Delta\).  
**Observation 2**.: Any \(\gamma\)-complete set in a graph with maximum degree \(\Delta\) has size at most \(\Delta/\gamma+1\).  
Thus, one may again reject instances where \(k\) is too big. Afterwards, for each \(k^{\prime}\in[k,\Delta/\gamma+1]\), we may solve \(\gamma\)-Complete Graph by solving \(s\)-Plex with the appropriate \(s\), as described above. Since \(s<k^{\prime}\leq\Delta/\gamma+1\), we immediately obtain the following.  
**Proposition 4**.: \(\gamma\)-Complete Graph _is fixed-parameter tractable with respect to the parameter \((\Delta,\gamma)\)._  
This just indicates that interesting tractability results are possible for \(\gamma\)-Complete Graph. Obtaining them for smaller parameters, such as the degeneracy of \(G\), would be clearly desirable. We mention in passing that for \(\gamma\geq 0.5\), there are close connections to connectivity-based clique relaxations, which we discuss in Section 5.