polynomial time algorithm can achieve an approximation factor better than for some unless P = NP. L-reductions The following two reductions show that the minimum dominating set problem and the set cover problem are equivalent under L-reductions: given an instance of one problem, we can construct an equivalent instance of the other problem. From dominating set to set covering Given a graph with construct a set cover instance as follows: the universe is , and the family of subsets is such that consists of the vertex and all vertices adjacent to in . Now if is a dominating set for , then is a feasible solution of the set cover problem, with . Conversely, if is a feasible solution of the set cover problem, then is a dominating set for , with . Hence the size of a minimum dominating set for equals the size of a minimum set cover for . Furthermore, there is a simple algorithm that maps a dominating set to a set cover of the same size and vice versa. In particular, an efficient algorithm for set covering provides an efficient algorithm for minimum dominating sets. For example, given the graph shown on the right, we construct a set cover instance with the universe and the subsets and In this example, is a dominating set for – this corresponds to the set cover For example, the vertex is dominated by the vertex , and the element is contained in the set . From set covering to dominating set Let be an instance of the set cover problem with the universe and the family of subsets we assume that and the index set are disjoint. Construct a graph as follows: the set of vertices is , there is an edge between each pair , and there is also an edge for each and . That is, is a split graph: is a clique and is an independent set. Now if is a feasible solution of the set cover problem for some subset , then is a dominating set for , with : First, for each there is an such that , and by construction, and are adjacent in ; hence is dominated by . Second, since must be nonempty, each is adjacent to a vertex in . Conversely, let be a dominating set for . Then it is possible to construct another dominating set such that and