# Multivariate Algorithmics for Finding Cohesive Subnetworks
## 4 Density-Based Clique Relaxations
### Relative Relaxation of the Density: \(\gamma\)-Quasi-Cliques  
A natural way of using the number of edges in a graph to measure cohesiveness is to divide this number by the number of edges in a clique of the same order. **Definition 9**: _The density of a graph \(G=(V,E)\) is \(2m/(n(n-1))\). A set \(S\) is a \(\gamma\)-quasi-clique if \(G[S]\) has density at least \(\gamma\)._  
This notion was proposed, among others, by [PERSON] _et al._[47]; \(\gamma\)-quasi-cliques are also referred to as \(\mu\)-_dense graphs_[8] or \(\mu\)-_cliques_[14]. The combination of \(\gamma\)-quasi-cliques and \(\gamma\)-complete graphs has also received interest [48]. An example of a 0.7-clique is shown in Figure 5. The \(\gamma\)-quasi-clique property is not hereditary: deleting, for example, \"Masil\" from the illustrated 0.7-quasi-clique results in a set whose induced subgraph has 10 out of 15 possible edges and, thus, density \(2/3<0.7\). In fact, the property is hereditary only for the two extreme cases \(\gamma=1\) (when only cliques fulfill the property) and \(\gamma=0\) (when every vertex set fulfills the property). The property is, however, quasi-hereditary for every \(\gamma\in[0,1]\): removing a vertex of minimum degree from a \(\gamma\)-quasi-clique results in another \(\gamma\)-quasi-clique [8; 49]. As for the other clique relaxations, we are interested in finding large \(\gamma\)-quasi-cliques. The \(\gamma\)-Quasi-Clique problem is NP-hard for all \(\gamma\in(0,1]\)[49]. Since the \(\gamma\)-quasi-clique property is quasi-hereditary, one may solve \(\gamma\)-Quasi-Clique by deciding whether \(G\) has a \(\gamma\)-quasi-clique of size _exactly_\(k\). Consequently, \(\gamma\)-Quasi-Clique can be directly reduced to Dense-k-Subgraph, where we aim to find a size-\(k\) set \(S\subseteq V\) such that \(G[S]\) has a maximum number of edges [50]. When considering the parameterized complexity of \(\gamma\)-Quasi-Clique, we face hardness for both solution size-related parameters. More precisely, for every \(\gamma\in(0,1]\), \(\gamma\)-Quasi-Clique is W[1]-hard with respect to \(k\) and W[1]-hard with respect to \(\ell\)[14]. Moreover, for every \(\gamma\in(0,1]\), \(\gamma\)-Quasi-Clique is W[1]-hard even for the combined parameter \((k,d)\) where \(d\) is the degeneracy of the input graph [14]. In contrast, fixed-parameter tractability can be obtained for the parameter maximum degree and also for the smaller parameter \(h\)-index. The fixed-parameter algorithms for both parameters are  
Figure 5: A part of the highland tribes social network [4]. The black vertices form the maximum 0.7-quasi-clique in this network. based on the following fact, which we state for the smallest of the three degree-based parameters under consideration. **Observation 4** ([14] (Lemma 4)). : If \(G\) has degeneracy \(d\), then for every fixed \(\gamma\in(0,1]\), every \(\gamma\)-quasi-clique in \(G\) has \(O(d)\) vertices. Clearly, the same statement holds for the maximum degree and the \(h\)-index of \(G\). Thus, the relevant values of \(k\) are bounded in the maximum degree \(\Delta\), in the \(h\)-index \(h\) and in the degeneracy \(d\) of the input graph \(G\). The constants hidden in the \(O\)-notation depend on \(\gamma\) and are different for each parameter. Observation 4 implies a polynomial-time algorithm for constant values of \(d\), but a fixed-parameter algorithm for \(d\) is unlikely (recall that \(\gamma\)-Quasi-Clique is W[1]-hard with respect to \((d,k)\)). For the parameters \(\Delta\) and \(h\), one can solve \(\gamma\)-Quasi-Clique in \(\Delta^{O(\Delta)}\cdot n^{O(1)}\) or in \(h^{O(h)}\cdot n^{O(1)}\) time [14]. An experimental evaluation and heuristic improvement of the corresponding fixed-parameter algorithm turned out to be competitive with a state-of-the art solver [51] when \(\gamma>0.5\), and the aim is to find _connected_\(\gamma\)-quasi-cliques [52]. Roughly speaking, for this task, the fixed-parameter algorithms for the parameter \(\Delta\) can find maximum \(\gamma\)-quasi-cliques of size \(k\approx 15\).