# A Brief Survey of Fixed-Parameter Parallelism
## 7 Parallel Algorithms Using FPT Methods
### Bounded Search Trees  
The idea behind our approach is that a fixed-parameter algorithm that is based on the bounded search tree approach will always run in \(FPP\)-time while branching, and could only violate the \(FPP\) condition when querying and updating the input, simply because a bounded search tree has a total number of nodes that is bounded by a function of the parameter. Typically, a bounded search tree algorithm would have a number of options, or possible branches, at each search-tree node. In most cases, and in what we shall assume in this section, this can be interpreted as a branching set \(S\) that is of size bounded by some constant. In the parallel algorithm, we set a master process to do the branching, while each of the other processes can supply the master with the needed set of elements to branch on. Since there are \(O(n^{|S|})\) sets of size \(|S|\), we need \(O(n^{|S|})\) processors, each of which will handle a set. A processor can identify its set simply by its rank. The approach entails keeping a global solution array of size bounded by some function of the parameter \(k\), usually linear in (or exactly equal to) \(k\) if we want a solution of size at most or at least \(k\). The solution array is kept in the master, and upon adding or removing an element from the solution, the other processes are informed by a reduction tree in logarithmic time, and that way all processes will always have the current solution stored locally. Depending on the problem in question, every process is responsible for a some subset of \(|S|\) elements and some condition for any of the elements to be in the solution. The process should forward the set of elements needed to satisfy the condition. If some elements cannot be forwarded due possibly to conflicts with the current (global) solution set, then only the valid elements are forwarded. An empty set is forwarded if the set is no longer valid as a branching set. By using a reduction tree method, we reduce the various sets of elements into one set. At step \(i\), starting from \(i=1\), a process whose index \(j\) is congruent to zero modulo \(2^{i}\) receives from the process whose index is \(j+2^{i-1}\). Therefore, we have established that each process will be responsible for a potential branching set of size \(|S|\) in such a way that each such subset of the input is included. These processes will be notified of which element was included in the solution set at each branch. Without loss of generality, in the case of \(d\)-Hitting Set (where \(d\) is a constant), each process will be responsible for a set of the input of size at most \(d\), while there would be a global solution set of size at most \(k\). At each branch, the process can check in \(d*k\) time whether its set has been hit by the existing solution set. If not, then this process forwards its set in a reduction tree manner along with other such processes. Eventually, the master process will either receive no set (or empty set) meaning that all input sets are covered by the existing solution set. The master may also receive a set that is not hit by the existing solution to branch on this set. In this manner, the master branching would always run in \(FPP\)-time since it is a bounded search tree algorithm. Querying the input sets, finding a set, and updating the input after including an element into the solution set are all \(FPP\) since each process is handling a specific input set. To generalize, if a process already has its set uncovered, then it forwards its set instead of the other process's set. This procedure repeats for \(log(n^{c})=c*log(n)\) steps where \(n^{c}\) is the number of processes, \(n\) is the input size, and \(c\) is a fixed constant. We can also apply certain comparison rules in order to return a set with given properties. We may, for example, return the largest or smallest set. In this case, all the master process has to do is to define a comparator method which the slaves will use to produce a final set for branching.