# A Brief Survey of Fixed-Parameter Parallelism
## 4 Key Results and Methods  
Since the emergence of the notion of parameterized parallel complexity and even before that, limited has been the scope of research on the topic, apart from experimental work that basically focused on scalability of parallel parameterized algorithms [13, 14]  
To the best of our knowledge, the first \(FPP\) algorithm dates back to 1988 and showed that the Feedback Vertex Set problem, on cyclically reducible digraphs, can be solved in \(O(k*log^{2}(n))\) time using \(O(n^{4})\) processors [15]. Of course, the notion of fixed-parameter parallelism was not known at that time. In addition, the problem at hand was not \(NP\)-hard, as is the case with common modern \(FPP\) algorithms. In fact, when parameterized parallel complexity was introduced in [1] (ten years later), it was shown that some known \(FPT\) problems can be \(PNC\) or even \(FPP\) if operations at every step are performed in \(PNC\)- or \(FPP\)-time respectively. Examples include Vertex Cover and Max Leaf Spanning Tree, among others. The approach used for these problems was kernelization, where each step is performed in \(FPP\)-time, and no more than \(k\) steps are performed, then a regular sequential algorithm is applied to the kernel. The aim was to prove \(FPP\) and \(PNC\) rather than achieving a most-efficient algorithm. The classical Vertex Cover kernel of [16] was used at the time, as a proof of concept, where all vertices of degree greater than the solution size \(k\) are removed in \(FPP\)-time, leaving a No instance or a kernel of order quadratic in \(k\). Using this notion of \(FPP\) kernelization followed by a sequential algorithm on the kernel, [PERSON] et al. [2] achieved a more efficient \(FPP\) algorithm for Vertex Cover. Crown reduction through maximal matching was used to obtain a kernel that is linear in \(k\) and an \(O(k^{3}\log(n)*1.2738^{k})\) algorithm for Vertex Cover using a polynomial number of processors. In addition to kernelization, color coding was applied, in an attempt to produce \(FPP\) algorithms. It was shown in [17] that a universal coloring family for a given input can be generated in constant parallel time. This coloring was then used to prove that several graph embedding, packing, covering, and clustering problems can be solved in efficient parallel time depending on the parameter \(k\). The algorithms were certainly not efficient or best-possible; however, they were enough to prove several problems \(FPP\) and \(PNC\). A third approach consisted of choosing an auxiliary parameter that is different form the solution size (which is often called the natural parameter). This work was mainly based on the work if [PERSON] and [PERSON] in [5], who showed that one can construct, in \(FPP\)-time, a tree decomposition of minimum width or decide that the tree-width is greater than the parameter \(k\). This paved the way for [PERSON] and [PERSON] [1] to prove several problems \(FPP\) when restricted to graphs of tree-width bounded by some parameter \(k\). Such problems are listed in [1] and include Hamiltonian Circuit, Hamiltonian Path, Chordal Graph Completion (fixed \(k\)), Dominating Set, Feedback Vertex Set, Feedback Arc Set, Longest Path, etc. The Feedback Vertex Set problem, for example, is in \(FPP\) since YES instance have a tree-width bounded by the parameter \(k\). More recently, the work reported in [18] adopted the graph modular width as auxiliary parameter. The Weighted Maximum Clique and the Maximum Matching problems were shown to be solvable in \(O(2^{k}*log(n))\) using \(O(n)\) processors, when the modular-width is bounded by \(k\). Along with proving problems \(FPP\), some problems were proved to be not in \(FPP\) or \(PNC\). The work reported in [1] showed how problems can be \(PNC\)-complete with respect to \(FPP\) reductions. The Bounded Size-Bounded Depth-Circuit Value problem (BS-BD-CVP), defined above, was used as a \(PNC\)-complete problem. Problems like the \(k\)-Clique were proved to be in \(NC\) but not in \(PNC\) to show these classes are not equal.