# A Brief Survey of Fixed-Parameter Parallelism
## 2 Preliminaries  
We assume familiarity with basic graph-theoretic terminology such as the notions described in [7]. In particular, given a simple undirected graph \(G=(V,E)\) and a vertex \(v\in V\) we denote by \(N(v)\) the set of neighbors of \(v\) and we define by \(N[v]=N(v)\cup\{v\}\) the closed neighborhood of \(v\) in \(G\). For a subset \(S\) of \(V\) we denote by \(N(S)\) the set \(\cup_{v\in S}N(v)\setminus S\), and we set \(N[S]=S\cup N(S)\). Moreover, the subgraph induced by \(S\) (i.e., the graph obtained by deleting all the elements of \(V\setminus S\) is denoted by \(G[S]\). \(S\) is a clique in \(G\) if \(G[S]\) is a complete subgraph (i.e., any two elements of \(S\) are adjacent in \(G\)). A clique on \(t\) vertices is denoted by \(K_{t}\). On the other hand, \(S\) is said to be independent or stable in \(G\) if no two elements of \(S\) are adjacent in \(G\). One of the most studied parameterized problems is Vertex Cover which, for a given graph \(G=(V,E)\) and a parameter \(k\), asks for a subset \(C\) of \(V\) of cardinality at most \(k\) whose complement is independent. In other words, every edge of \(G\) has at least one endpoint in \(C\). Vertex Cover is among the first classical problems shown to be fixed-parameter tractable [3]. A closely related problem is Clique, which for a given graph \(G\) and a parameter \(k\), asks whether \(G\) has a clique of size at least \(k\). From a parameterized complexity standpoint, Clique is equivalent to Independent Set due a straightforward transformation of the input, without changing the parameter. Both problems are \(W[1]\)-complete. One of the reasons why Vertex Cover is popular, and not as \"hard\" as other parameterized problems, stems from the fact that it is a special case of many (more general) problems. It is a (i) deletion into maximum-degree \(d\) where \(d=0\), (ii) deletion into connected components of size \(p\) where \(p=1\), and (iii) deletion into \(K_{t}\)-free graphs for \(t=2\), among other generalizations. A closely related problem is deletion into cycle-free graphs: in the Feedback Vertex Set (FVS) problem we ask for a subset \(C\) of \(V\) of cardinality at most \(k\) such that \(V\setminus C\) has no cycles. \(FVS\) is fixed-parameter tractable. A tree decomposition of a given graph \(G=(V,E)\) is a tree \(T\), whose nodes are subsets of \(V\). To avoid confusion, vertices of \(G\) and \(T\) are referred to as vertices and nodes, respectively. Let the set of nodes of \(T\) be \(X=\{X_{1},X_{2},\cdots\}\), the following properties should hold:  
1. Every vertex of \(G\) is present in at least one node in \(T\). Moreover \(\bigcup X_{i}=V\). 2. The nodes of \(T\) containing some vertex \(v\) form a connected subtree. In other words, if \(X_{i}\) and \(X_{j}\) both contain a vertex \(v\), then every node \(X_{k}\) along the unique path between \(X_{i}\) and  
intractable problems can be solved in polynomial time on graphs of bounded treewidth. It would thus be interesting to try to utilize the tree-like structure to design fixed-parameter algorithms for problems parameterized by treewidth, whenever possible. Another parameter that has been recently used in the design of parameterized parallel algorithms is modular-width, which is related to the modular decomposition of a graph, introduced in [9]. In a modular decomposition, the graph is decomposed into modules, also called autonomous, homogeneous, or partitive sets. A module \(X\) in a graph \(G\) satisfies: \(\forall u,v\in X,N(u)\setminus X=N(v)\setminus X\). The notion of a module obviously generalizes that of a connected component, but it should be noted that modules can be subsets of each other. A modular decomposition is a recursive division of the graph into modules, in which 4 steps defined in [9] are applied recursively to the graph, where steps can generate modules, until a tree of modules is obtained with one-element sets as its leaves. Modular width was defined in [10] as the maximum degree of the optimal modular decomposition tree.