Dominating set problem

Problem definition

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 $\gamma(G)$ is the number of vertices in a smallest dominating set for $G$. The decision version of finding the minimum dominating set is an NP-complete. In the following, we are going to solve the dominating set problem on the Petersen graph.

using GenericTensorNetworks, Graphs

graph = Graphs.smallgraph(:petersen)

{10, 15} undirected simple Int64 graph

We can visualize this graph using the following function

rot15(a, b, i::Int) = cos(2i*π/5)*a + sin(2i*π/5)*b, cos(2i*π/5)*b - sin(2i*π/5)*a
locations = [[rot15(0.0, 60.0, i) for i=0:4]..., [rot15(0.0, 30, i) for i=0:4]...]
show_graph(graph, locations; format=:svg)

Generic tensor network representation

We can use DominatingSet to construct the tensor network for solving the dominating set problem as

dom = DominatingSet(graph)

DominatingSet{SimpleGraph{Int64}, Int64, UnitWeight}(SimpleGraph{Int64}(15, [[2, 5, 6], [1, 3, 7], [2, 4, 8], [3, 5, 9], [1, 4, 10], [1, 8, 9], [2, 9, 10], [3, 6, 10], [4, 6, 7], [5, 7, 8]]), [1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

The tensor network representation of the dominating set problem can be obtained by

problem = GenericTensorNetwork(dom; optimizer=TreeSA())

GenericTensorNetwork{DominatingSet{SimpleGraph{Int64}, Int64, UnitWeight}, OMEinsum.SlicedEinsum{Int64, OMEinsum.DynamicNestedEinsum{Int64}}, Int64}
- open vertices: Int64[]
- fixed vertices: Dict{Int64, Int64}()
- contraction time = 2^11.119, space = 2^8.0, read-write = 2^11.334

where the key word argument optimizer specifies the tensor network contraction order optimizer as a local search based optimizer TreeSA.

Theory (can skip)

Let $G=(V,E)$ be the target graph that we want to solve. The tensor network representation map a vertex $v\in V$ to a boolean degree of freedom $s_v\in\{0, 1\}$. We defined the restriction on a vertex and its neighboring vertices $N(v)$:

\[T(x_v)_{s_1,s_2,\ldots,s_{|N(v)|},s_v} = \begin{cases} 0 & s_1=s_2=\ldots=s_{|N(v)|}=s_v=0,\\ 1 & s_v=0,\\ x_v^{w_v} & \text{otherwise}, \end{cases}\]

where $w_v$ is the weight of vertex $v$. This tensor means if both $v$ and its neighboring vertices are not in $D$, i.e., $s_1=s_2=\ldots=s_{|N(v)|}=s_v=0$, this configuration is forbidden because $v$ is not adjacent to any member in the set. otherwise, if $v$ is in $D$, it has a contribution $x_v^{w_v}$ to the final result. One can check the contraction time space complexity of a DominatingSet instance by typing:

contraction_complexity(problem)

Time complexity: 2^11.118941072723507
Space complexity: 2^8.0
Read-write complexity: 2^11.33371442609397

Solving properties

Counting properties

Domination polynomial

The graph polynomial for the dominating set problem is known as the domination polynomial (see arXiv:0905.2251). It is defined as

\[D(G, x) = \sum_{k=0}^{\gamma(G)} d_k x^k,\]

where $d_k$ is the number of dominating sets of size $k$ in graph $G=(V, E)$.

domination_polynomial = solve(problem, GraphPolynomial())[]

The domination number $\gamma(G)$ can be computed with the SizeMin property:

domination_number = solve(problem, SizeMin())[]

3.0ₜ

Similarly, we have its counting CountingMin:

counting_min_dominating_set = solve(problem, CountingMin())[]

(3.0, 10.0)ₜ

Configuration properties

finding minimum dominating set

One can enumerate all minimum dominating sets with the ConfigsMin property in the program.

min_configs = read_config(solve(problem, ConfigsMin())[])

all(c->is_dominating_set(graph, c), min_configs)

true

show_configs(graph, locations, reshape(collect(min_configs), 2, 5); padding_left=20)

Similarly, if one is only interested in computing one of the minimum dominating sets, one can use the graph property SingleConfigMin.

This page was generated using Literate.jl.