Dominating set
In graph theory, a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is in D, or has a neighbor in D. The domination number γ(G) is the number of vertices in a smallest dominating set for G. The dominating set problem concerns testing whether γ(G) ≤ K for a given graph G and input K; it is a classical NP-complete decision problem in computational complexity theory.
They have also been used in document summarization, and in designing secure systems for electrical grids.
A more interesting challenge is to find small dominating sets.
If S is a connected dominating set, one can form a spanning tree of G in which S forms the set of non-leaf vertices of the tree; conversely, if T is any spanning tree in a graph with more than two vertices, the non-leaf vertices of T form a connected dominating set.
For example, a graph with one or more vertices and no edges does not have a total dominating set.
An (1 + log n)-approximation of a minimum k-tuple dominating set can be found in polynomial time.
A star-dominating set is a subset D of V such that, for every vertex v in V, the star of v (the set of edges adjacent to v) intersects the star of some vertex in D. Clearly, if G has isolated vertices then it has no star-dominating sets (since the star of isolated vertices is empty).
The distinction between star-domination and usual domination is more substantial when their fractional variants are considered.
Equivalently, it is the size of the smallest maximal independent set.
For example, let G be the double star graph consisting of vertices
For example, if the vertices of G are all the subsets of squares of an n-by-n board, then still iγ(G) = 1, but γ(G) = n.[8] The bi-independent domination number iγi(G) of a graph G is the maximum, over all independent sets A of G, of the smallest independent set dominating A.
In 1972, Richard Karp proved the set cover problem to be NP-complete.
[10] 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 α-approximation algorithm for minimum dominating sets would provide a polynomial-time α-approximation algorithm for the set cover problem and vice versa.
More specifically, the greedy algorithm provides a factor 1 + log|V| approximation of a minimum dominating set, and no polynomial time algorithm can achieve an approximation factor better than c log|V| for some c > 0 unless P = NP.
[10] Given a graph G = (V, E) with V = {1, 2, ..., n}, construct a set cover instance (U, S) as follows: the universe U is V, and the family of subsets is S = {S1, S2, ..., Sn} such that Sv consists of the vertex v and all vertices adjacent to v in G. Now if D is a dominating set for G, then C = {Sv : v ∈ D} is a feasible solution of the set cover problem, with |C| = |D|.
In particular, an efficient α-approximation algorithm for set covering provides an efficient α-approximation algorithm for minimum dominating sets.
Now if C = {Si : i ∈ D} is a feasible solution of the set cover problem for some subset D ⊆ I, then D is a dominating set for G, with |D| = |C|: First, for each u ∈ U there is an i ∈ D such that u ∈ Si, and by construction, u and i are adjacent in G; hence u is dominated by i.
Then C = {Si : i ∈ X} is a feasible solution of the set cover problem, with |C| = |X| ≤ |D|.
Also, let dg be the cardinality of dominating set obtained using greedy approximation then following relation holds,
[13] For fixed Δ, this qualifies as a dominating set for APX membership; in fact, it is APX-complete.
[15] A minimum dominating set can be found in linear time in series–parallel graphs.
[16] A minimum dominating set of an n-vertex graph can be found in time O(2nn) by inspecting all vertex subsets.
Fomin, Grandoni & Kratsch (2009) show how to find a minimum dominating set in time O(1.5137n) and exponential space, and in time O(1.5264n) and polynomial space.
A faster algorithm, using O(1.5048n) time was found by van Rooij, Nederlof & van Dijk (2009), who also show that the number of minimum dominating sets can be computed in this time.
[17] Finding a dominating set of size k plays a central role in the theory of parameterized complexity.
In particular, the problem is not fixed-parameter tractable in the sense that no algorithm with running time f(k)nO(1) for any function f 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 k,[18] and running times that are exponential in √k and cubic in n may be obtained by applying dynamic programming to a branch-decomposition of the kernel.
[19] More generally, the dominating set problem and many variants of the problem are fixed-parameter tractable when parameterized by both the size of the dominating set and the size of the smallest forbidden complete bipartite subgraph; that is, the problem is FPT on biclique-free graphs, a very general class of sparse graphs that includes the planar graphs.
