set dominating . Dominating subsets of vertices requires potentially less vertices than dominating all vertices, so for all graphs . The inequality can be strict - there are graphs for which . For example, for some integer , let be a graph in which the vertices are the rows and columns of an -by- board, and two such vertices are connected if and only if they intersect. The only independent sets are sets of only rows or sets of only columns, and each of them can be dominated by a single vertex (a column or a row), so . However, to dominate all vertices we need at least one row and one column, so . Moreover, the ratio between can be arbitrarily large. For example, if the vertices of are all the subsets of squares of an -by- board, then still , but . The bi-independent domination number of a graph is the maximum, over all independent sets of , of the smallest independent set dominating . The following relations hold for any graph : History The domination problem was studied from the 1950s onwards, but the rate of research on domination significantly increased in the mid-1970s. In 1972, Richard Karp proved the set cover problem to be NP-complete. This had immediate implications for the dominating set problem, as there are straightforward vertex to set and edge to non-disjoint-intersection bijections between the two problems. This proved the dominating set problem to be NP-complete as well. Algorithms and computational complexity The set cover problem is a well-known NP-hard problem – the decision version of set covering was one of Karp's 21 NP-complete problems. There exist a pair of polynomial-time L-reductions between the minimum dominating set problem and the set cover problem. These reductions (see below) show that an efficient algorithm for the minimum dominating set problem would provide an efficient algorithm for the set cover problem, and vice versa. Moreover, the reductions preserve the approximation ratio: for any α, a polynomial-time algorithm for minimum dominating sets would provide a polynomial-time algorithm for the set cover problem and vice versa. Both problems are in fact Log-APX-complete. The approximability of set covering is also well understood: a logarithmic approximation factor can be found by using a simple greedy algorithm, and finding a sublogarithmic approximation factor is NP-hard. More specifically, the greedy algorithm provides a factor approximation of a minimum dominating set, and no