# Multivariate Algorithmics for Finding Cohesive Subnetworks
## 1 Introduction
### Multivariate Algorithmics  
Parameterized and multivariate algorithmics aim at a refined complexity analysis of hard computational problems [15; 16]. To this end, each input \(I\) is equipped with an additional parameter \(p\), usually a nonnegative integer. The central idea is to exploit situations in which the value of the parameter \(p\) is small. This is captured by the central definition in parameterized algorithmics. **Definition 4**. : A parameterized problem \(L\) is _fixed-parameter tractable_ if every instance \((I,p)\) of \(L\) can be solved in \(f(p)\cdot|I|^{O(1)}\) time, where \(f\) is a computable function depending only on \(p\). Algorithms that achieve such a running time are called _fixed-parameter algorithms_. The idea behind the definition is that for small values of \(p\), the problem can be solved efficiently as the exponential part of the running time depends only on \(k\). In the context of parameterized algorithmics, the term _multivariate_ refers to the fact that there is not only one interesting parameter, but that several different parameters and combinations of parameters may be potentially interesting [17; 18]. Of course, not all parameterized problems are fixed-parameter tractable. This is obvious for problems that are NP-hard for constant parameter values, such as SAT with the parameter clause size. There are, however, also problems that can be solved in polynomial time for every constant parameter value (that is, in \(|I|^{f(k)}\) time for some computable \(f\)), but that resist any attempts to devise fixed-parameter algorithms. There are two complexity-theoretic assumptions that are used to show that fixed-parameter algorithms are unlikely for such problems. [PERSON] and [PERSON] [15] developed a theory of parameterized intractability by defining the so-called W-hierarchy of problems that are unlikely to be fixed-parameter tractable. The basic class of intractability is W[1], that is, the central conjecture is W[1]\(\
eq\) FPT where FPT is the class of fixed-parameter tractable problems. Thus, if a problem is W[1]-hard, it is unlikely to be fixed-parameter tractable; W[1]-hardness of a parameterized problem \(L\) can be shown via a parameterized reduction from a W[1]-hard problem \(L^{\prime}\); for a definition of parameterized reduction, refer to [15; 16]. For the problem of finding large subgraphs fulfilling a hereditary graph property \(\Pi\), there exists the following general W[1]-hardness result. **Theorem 2** ([19]). : _Let \(\Pi\) be a hereditary graph property that does not contain all independent sets. Then, given an undirected graph \(G=(V,E)\) and integer \(k\), deciding whether there is a size-\(k\) set \(S\subseteq V\) such that \(G[S]\in\Pi\) is W[1]-hard with respect to \(k\)._  
Since any sensible clique relaxation has to exclude independent sets that are too large, Theorem 2 applies if the property of the clique relaxation is hereditary. More fine-grained running time lower bounds can be achieved via assuming the so-called exponential-time hypothesis (ETH) [20]. The ETH states that 3-SAT cannot be solved in \(2^{o(n)}\) time, where \(n\) is the number of variables in the input formula. The ETH implies W[1]\(\
eq\) FPT, but the converse is not known to be true. Consequently, the ETH can be regarded as a stronger assumption. An even stronger assumption that yields even more refined running time bounds is the strong exponential-time hypothesis (SETH), which essentially states that CNF-SAT cannot be solved in \((2-\epsilon)^{n}\cdot|I|^{O(1)}\) time for any \(\epsilon>0\)[20]. The Clique Problem from the Viewpoint of Multivariate Algorithmics  
Let us quickly review the complexity of Clique with respect to the parameters defined above: the clique size \(k\), the dual parameter \(\ell:=n-k\), and the maximum degree \(\Delta\), degeneracy \(d\) and \(h\)-index of \(G\). The natural parameter for Clique is the size \(k\) of the clique. For this parameter, Cliqueis W[1]-hard [15]; in fact, Clique is the most prominent W[1]-hard problem.