# A Brief Survey of Fixed-Parameter Parallelism
## 1 Introduction  
Similarly to how computational problems are classified according to their tractability or whether efficient algorithms exist for them, problems are also classified according to whether efficient parallel algorithms exist to solve them. The \(NC\) class and the corresponding \(NC^{i}\) hierarchy have been used to classify \"efficiently parallelizable\" problems that lie in the class \(P\). With the rise of parameterized complexity theory and the notion of fixed-parameter tractability (\(FPT\)), the class \(PNC\) was introduced as analogous to the class \(NC\) in the field of parameterized complexity. This notion was then extended to introduce the class fixed-parameter parallelizable (\(FPP\)) in [1]. More recently, a refined version of \(FPP\), dubbed fixed-parameter parallel tractable (\(FPT\)) was also introduced in [2].  
Since the introduction of the notion of parameterized parallel complexity, a few articles have been published to study a variety of parameterized problems. Typically, a problem is either shown to be efficiently parallelizable or impossible to efficiently parallelize with respect to various parameters such as the solution size (or natural parameter), tree-width, modular-width, etc. In this paper, we survey the existing complexity classes and algorithmic methodologies, and we provide a number of observations about the various techniques and classes.  
Throughout this paper we mainly consider parameterized problems. An instance of a parameterized problem is of the form \((X,k)\) where \(X\) is the problem input and \(k\) is the parameter, which is often a bound on the size of a desired solution. A parameterized problem \((X,k)\) is fixed-parameter tractable (FPT): if it can be solved in \(O(f(k)*n^{c})\) time where \(n\) is the input size (\(n=|X|\)) and \(c\) is a fixed constant, independent of \(n\) and \(k\)[3].  
From a classical parallel complexity standpoint, the class \(NC\), or _[PERSON]'s class_, is known to be analogous to the class \(P\) (in sequential complexity). In short, a parallel problem is in \(NC\) if it can be solved in \(O(log^{c_{1}}(n))\) time using \(O(n^{c_{2}})\) processors, where \(c_{1}\) and \(c_{2}\) are constants [4]. To convert this notion into a parameterized definition that we can use (or relate to) later, and following the same assumptions of [1], we consider a parameterized problem to be in \(NC\) if it is in \(NC\) for any given value of the parameter. By this definition, a problem parameterized by \(k\) (independent of \(n\)) is in \(NC\) if it is solvable in \(O(f_{1}(k)*log^{f_{2}(k)}(n))\) time using \(O(f_{3}(k)*n^{f_{4}(k)})\) processors, where \(f_{1},f_{2},f_{3},f_{4}\), being functions of \(k\), are independent of \(n\) and are considered in this case constants with respect to \(n\) to abide by the original \(NC\) definition above.  
The first parameterized parallel complexity class, defined in [5] and viewed as the parameterized analog to NC, is \(PNC\). Membership in PNC requires the problem to be solvable in \(\mathcal{O}\left(f(k)\cdot(\log n)^{h(k)}\right)\) using \(\mathcal{O}\left(g(k)\cdot n^{\theta}\right)\) processors. The more restrictive class of _fixed-parameter parallel_ (\(FPP\)) problems was defined by [PERSON] and [PERSON] in [1] where a strictly poly-logarithmic factor in the running time is required, by replacing \(h(k)\) with a constant. More recently, it was observed in [6] that the function \(g(k)\) in the number of processors is redundant. A corresponding refined version of \(FPP\) was defined in [2] under the (also refined) name: _fixed-parameter parallel tractable_, or \(FPPT\). In this paper we survey the various methods used in the area of parameterized parallel complexity and present the results known so far for all the studied problems in this area. Relations between the various complexity classes are also presented along with new observations and results. In particular we overview the methods used for obtaining a parameterized parallel algorithm from a known sequential fixed-parameter algorithm.