# Multivariate Algorithmics for Finding Cohesive Subnetworks
## 6 Conclusions
It would thus be very interesting to find a further parameter that is now sandwiched between \(h\)-index and degeneracy and to obtain positive algorithmic results for this parameter. Most implementations of efficient algorithms that find cohesive subgraphs based on clique relaxations are developed purely for experimental purposes and often based on mathematical programming approaches. This may limit their appeal to users that expect a flexible tool providing good algorithms for a large collection of models of cohesive subgraphs. Developing such a tool is a challenging task. Connectivity-based clique relaxations have received the least interest so far, both from a theoretical and a practical point of view. Hence, this class of clique relaxation yields the most open field for future research. As the minimum connectivity of a graph is a structurally more restrictive (or \"deep\") property than, for example, its minimum degree, efficient fixed-parameter algorithms are likely to rely on new techniques. This survey and most parts of the literature study clique relaxations only in undirected graphs. Applications of clique relaxations in directed graphs or graphs with different types of edges (such as the original highland tribes network [4] and many other social networks) should give rise to many further interesting computational problems. In addition to the subgraph problems considered in this work, clique relaxations also find application in graph clustering and graph partitioning problems [53; 57; 59; 60; 61; 62; 63]. In the corresponding computational problems, one searches for a partition of the vertex set of the input graph such that each part of the partition represents a cohesive group. As for subgraph problems, depending on the application, it may be appropriate to use different clique relaxations as models for cohesive groups. A typical optimization goal would be to maximize the overall number of edges of the input graph that have both endpoints within the same part (this is often called edge coverage). A systematic study of the relation between the complexity of such clustering problems and the used clique relaxations is still lacking. Finally, a further related avenue yielding many interesting computational problems is to consider concepts and parameterizations that take the edges between \(S\) and \(V\setminus S\) into account. One example of such concepts are _alliances_[64; 65], which are, roughly speaking, vertex sets \(S\) such that every vertex of \(S\) has more neighbors in \(S\) than outside of \(S\). Finding various types of alliances of size \(k\) is fixed-parameter tractable with respect to \(k\)[66; 67]. A multivariate complexity study, however, is lacking. Moreover, the known fixed-parameter algorithms for these problems have running time \(k^{\Theta(k)}\cdot n^{O(1)}\). Therefore, running time improvements or tight running time lower bounds are desirable. One idea here could be to mix clique relaxations and alliances, that is, to consider types of alliances that fulfill cohesiveness demands. This might yield efficient algorithms to identify certain types of alliances. A related field would be to systematically investigate the combination of clique relaxations and isolation concepts [24; 27; 58; 68], where the number of outgoing edges from a set \(S\) is restricted. To summarize, studies for degree-based [27; 29], distance-based [43; 44] and density-based [14; 52] clique relaxations show that clique relaxations are a rewarding working area for multivariate algorithms: problems related to clique relaxations may admit fixed-parameter algorithms that can be tuned to yield competitive algorithms in practice. Consequently, we feel that the combination of multivariate algorithmics and clique relaxations will remain a relevant and challenging field of study in the near future. The abundance of freely available data makes this area particularly suitable to the implementation of fixed-parameter algorithms and their experimental analysis.