# Multivariate Algorithmics for Finding Cohesive Subnetworks
## 1 Introduction
### Preliminaries  
In this section, we first describe the notation and present some basic graph-theoretic definitions used throughout this work. Then, we give a very brief introduction to multivariate algorithmics, in particular to the complexity-theoretic framework used to show intractability. Finally, we discuss the multivariate complexity of Clique with respect to the parameters under consideration in this survey. Notation, Basic Definitions and Basic Results  
We consider undirected graphs \(G=(V,E)\) where \(V\) is the vertex set and \(E\subseteq\{\{u,v\}\mid u,v\in V\}\) is the edge set of the graph. We let \(n:=|V|\) and \(m:=|E|\) denote the number of vertices and edges in the graph \(G\), respectively. The _(open) neighborhood_ of a vertex \(v\) is denoted by \(N(v):=\{u\mid\{u,v\}\in E\}\) and the _closed neighborhood_ by \(N[v]:=N(v)\cup\{v\}\). For a vertex set \(S\subseteq V\)let \(G[S]:=(S,\{\{u,v\}\in E\mid u,v\in S\})\) denote the _subgraph of \(G\) induced by \(S\)_. For a vertex set \(S\subseteq V\), let \(G-S:=G[V\setminus S]\) denote the induced subgraph of \(G\) obtained by deleting the vertices of \(S\) and their incident edges. Similarly, for a vertex \(v\in V\), let \(G-v:=G-\{v\}\) denote the graph obtained by deleting this vertex and all its incident edges. A vertex set \(D\subseteq V\) in a graph \(G=(V,E)\) is _dominating_ if every vertex of \(G\) is either contained in \(D\) or has a neighbor in \(D\). The _complement graph_\(\vec{G}\) of a graph \(G=(V,E)\) is \((V,\{\{u,v\}\mid u,v\in V\wedge u\
eq v\wedge\{u,v\}\
otin E\})\). For two vertices \(u\) and \(v\) in a graph \(G\), let \(\operatorname{dist}_{G}(u,v)\) denote the length (that is, the number of edges) of a shortest path between \(u\) and \(v\) in \(G\). The _diameter of a graph_ is the maximum value of \(\operatorname{dist}_{G}(u,v)\) over all \(u,v\in V\). The _\(k\)-th power_ of a graph \(G=(V,E)\) is the graph \(G^{k}:=(V,\{\{u,v\}\mid u\
eq v\wedge\operatorname{dist}_{G}(u,v)\leq k\})\). The _closed \(k\)-neighborhood_ of a vertex \(v\) in a graph \(G\) is the set \(N_{k}[v]:=\{u\in V\mid\operatorname{dist}_{G}(u,v)\leq k\}\). Formally, clique relaxations are vertex sets fulfilling certain properties in a graph, and thus, they are closely related to _graph properties_. (Most clique relaxations can be defined either as graphs or as vertex sets within some graph. One exception are \(s\)-cliques discussed in Section 3. To make the definitions coherent, we use definitions based on vertex sets.) An important feature of a graph property is whether or not it is closed under vertex deletion. **Definition 2**. : A graph property \(\Pi\) is _hereditary_ if for every graph \(G=(V,E)\) fulfilling \(\Pi\) and every vertex \(v\in V\), the graph \(G-v\) also fulfills \(\Pi\). We extend this definition to vertex sets \(S\) in the natural way, that is, a property on vertex sets is hereditary if the following holds: if a set \(S\subseteq V\) fulfills the property, then so does every \(S^{\prime}\subseteq S\). Many graph properties tied to clique relaxations are hereditary. Thus, from the following classic result on vertex deletion problems, we can directly infer the NP-hardness of many problems related to clique relaxations. **Theorem 1** ([13]). : _For every nontrivial hereditary graph property \(\Pi\), the problem of deciding whether at most \(\ell\) vertices can be deleted from a graph \(G\) to obtain a graph \(G^{\prime}\) that fulfills \(\Pi\) is NP-hard._  
Hereditary graph properties allow for the deletion of _any_ vertex. A weaker, but still useful feature of graph properties is being quasi-hereditary, also called nested [8]. **Definition 3**. : A graph property \(\Pi\) is _quasi-hereditary_ if for every graph \(G=(V,E)\) fulfilling \(\Pi\), there is a vertex \(v\in V\), such that the graph \(G-v\) also fulfills \(\Pi\). The following is based on an algorithm that enumerates all connected subgraphs of order \(k\) in degree-bounded graphs [14]. For the sake of completeness, we give a short proof. **Proposition 1**.