: simply replace each by a neighbour of . Then is a feasible solution of the set cover problem, with . The illustration on the right show the construction for and In this example, is a set cover; this corresponds to the dominating set is another dominating set for the graph . Given , we can construct a dominating set which is not larger than and which is a subset of . The dominating set corresponds to the set cover Special cases If the graph has maximum degree Δ, then the greedy approximation algorithm finds an -approximation of a minimum dominating set. Also, let be the cardinality of dominating set obtained using greedy approximation then following relation holds, , where is number of nodes and is number of edges in given undirected graph. For fixed Δ, this qualifies as a dominating set for APX membership; in fact, it is APX-complete. The problem admits a polynomial-time approximation scheme (PTAS) for special cases such as unit disk graphs and planar graphs. A minimum dominating set can be found in linear time in series–parallel graphs. Exact algorithms A minimum dominating set of an -vertex graph can be found in time by inspecting all vertex subsets. show how to find a minimum dominating set in time and exponential space, and in time and polynomial space. A faster algorithm, using time was found by , who also show that the number of minimum dominating sets can be computed in this time. The number of minimal dominating sets is at most and all such sets can be listed in time . Parameterized complexity Finding a dominating set of size plays a central role in the theory of parameterized complexity. It is the most well-known problem complete for the class W[2] and used in many reductions to show intractability of other problems. In particular, the problem is not fixed-parameter tractable in the sense that no algorithm with running time for any function exists unless the W-hierarchy collapses to FPT=W[2]. On the other hand, if the input graph is planar, the problem remains NP-hard, but a fixed-parameter algorithm is known. In fact, the problem has a kernel of size linear in , and running times that are exponential in and cubic in may be obtained by applying dynamic programming to a branch-decomposition of the kernel. More generally, the dominating set problem and many variants of the problem are