# Calculate minimum dominating sets

This blog takes notes of dominating sets and shows how to calculate its value with the Python package, NetworkX.

# 1. Definitions, examples and applications

(1) Definitions

Excerpt from the Wikipedia article Dominating set

In graph theory, a dominating set for a graph G = (VE) is a subset D of V such that every vertex not in D is adjacent to at least one member of D. The domination number γ(G) is the number of vertices in a smallest dominating set for G.

(2) Examples

As shown in the following figures (a)-(d), in each example, each gray vertex is adjacent to at least one red vertex (the Grey vertex is dominated by the red vertex).

Fig. 1: Examples of dominating sets for a graph

(3) Applications

Dominating sets are useful in routing problems. What is the minimum routers needed for a network? This question can be reworded to calculate a
minimum dominating set.

A Connected Dominating Set (CDS) has been proposed to serve as a virtual backbone of wireless ad hoc networks (no fixed infrastructure or centralized management). The CDS of a graph representing a network has a significant impact on the efficient design of routing protocols in wireless networks[3].

# 2. Dominating set problems

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 (Garey & Johnson 1979).

Therefore it is believed that there is no efficient algorithm that finds a smallest dominating set for a given graph.

Luckily, several approximation algorithms have been proposed to search the minimum dominating set of a graph and some of them are available in NetworkX.

## 2.1 Find a dominating set

(1) Decision problem
is_dominating_set(G, nbunch), checks if nodes in nbunch are a dominating set for G.

(2) Find a dominating set

dominating_set(G, start_with=None), finds a dominating set for the graph G. Refer to the section 2: Algorithm 7 in [4] for the detailed description.

Note that this method does not guarantee of the minimum dominating sets though iterating all nodes as start_with (can not guarantee that all possible dominating sets are returned). For instance,

Fig. 2: The minimum dominating set of a graph

As we can see, the minimum dominating set is [c, d]. Running the following program, however, the domination number is 3.

def build_graph(self):
"""build up a graph"""

G = nx.Graph()

return G

def get_dominating_sets(self, G):
"""get all possible dominating sets by iterating all nodes"""
dominating_sets = set() # list of sets

for start_with in G:
dominating_set = frozenset(nx.dominating_set(G, start_with))  #　sets of sets, the inner sets must be frozenset objects.

return dominating_sets

# output
set([frozenset(['a', 'b', 'e', 'f']), frozenset(['c', 'e', 'f']), frozenset(['a', 'b', 'd'])])


## 2.2 Minimum dominating sets

min_weighted_dominating_set(G, weight=None), returns a dominating set that approximates the minimum weight node dominating set.

Vazirani, Vijay V. Approximation Algorithms. Springer Science & Business Media, 2001.

Using the method to calculate the approximate minimum dominating set over Fig. 1.

import networkx as nx

# tackle the issue: AttributeError: 'module' object has no attribute 'min_weighted_dominating_set'
import networkx.algorithms.approximation as nxaa

# build up a graph
G = nx.Graph()

# output
>>> nx.dominating_set(G)    # return a dominating sets
set(['a', 'e', 'f'])

>>> nxaa.min_weighted_dominating_set(G, weight=None)
set(['a', 'd'])

>>> nxaa.min_edge_dominating_set(G)
set([('a', 'c'), ('b', 'd')])


# 3. Edge dominating sets

In graph theory, an edge dominating set for a graph G = (VE) is a subset D ⊆ E such that every edge not in D is adjacent to at least one edge in D. An edge dominating set is also known as a line dominating set.

Here is an example.

Fig. 3: A edge dominating set of a graph

min_edge_dominating_set(G), returns minimum cardinality edge dominating set (an approximate solution to the edge dominating set problem).

References:
[1]Wikipedia: Dominating set
[2]Mathematics Stack Exchange: Real world application of dominating set?
[3]THAI, My T., WANG, Feng, LIU, Dan, et al. Connected dominating sets in wireless networks with different transmission ranges. Mobile Computing, IEEE Transactions on, 2007, vol. 6, no 7, p. 721-730.
[4]ESFAHANIAN, Abdol–Hossein. Connectivity algorithms. 2010. pdf
[5]StackOverflow: Networkx is unable to find some packages (version 1.10)
[6]Wikipedia: edge dominating set