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 = (V, E) 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()

    G.add_path(['a', 'c', 'd', 'e'])
    G.add_path(['b', 'c', 'd', 'f'])

    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.
        dominating_sets.add(dominating_set)

    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()
G.add_path(['a', 'b', 'd', 'f'])
G.add_path(['a', 'c', 'e', 'd', 'f'])

# 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 = (V, E) 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

赞赏

微信赞赏支付宝赞赏