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{UnitWeight}(Graphs.SimpleGraphs.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]]), UnitWeight())

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

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

GenericTensorNetwork{DominatingSet{UnitWeight}, OMEinsum.SlicedEinsum{Int64, OMEinsum.DynamicNestedEinsum{Int64}}, Int64}(DominatingSet{UnitWeight}(Graphs.SimpleGraphs.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]]), UnitWeight()), OMEinsum.SlicedEinsum{Int64, OMEinsum.DynamicNestedEinsum{Int64}}(Int64[], 2∘10∘7∘9, 2∘9∘10∘7 -> 
├─ 4∘6∘7∘9, 7∘9∘2∘4∘10∘6 -> 2∘10∘7∘9
│  ├─ 4∘6∘7∘9
│  └─ 10∘7∘6∘9∘3∘2∘8∘4, 3∘6∘10∘8 -> 7∘9∘2∘4∘10∘6
│     ├─ 5∘10∘3∘2∘7∘8∘1∘4, 3∘4∘8∘2∘1∘6∘5∘9 -> 10∘7∘6∘9∘3∘2∘8∘4
│     │  ├─ 7∘8∘1∘4∘5∘10, 1∘7∘4∘8∘3∘2 -> 5∘10∘3∘2∘7∘8∘1∘4
│     │  │  ├─ 5∘7∘8∘10, 1∘4∘10∘5 -> 7∘8∘1∘4∘5∘10
│     │  │  │  ⋮
│     │  │  │  
│     │  │  └─ 1∘3∘7∘2, 2∘4∘8∘3 -> 1∘7∘4∘8∘3∘2
│     │  │     ⋮
│     │  │     
│     │  └─ 3∘5∘9∘4, 8∘9∘2∘5∘1∘6 -> 3∘4∘8∘2∘1∘6∘5∘9
│     │     ├─ 3∘5∘9∘4
│     │     └─ 1∘8∘9∘6, 2∘5∘6∘1 -> 8∘9∘2∘5∘1∘6
│     │        ⋮
│     │        
│     └─ 3∘6∘10∘8
└─ 2∘9∘10∘7
), Dict{Int64, Int64}())

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.011227255423254
Space complexity: 2^8.0
Read-write complexity: 2^11.129926933510392

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.