Dominating Set Problem

Overview

A dominating set in graph theory is a subset D of vertices where every vertex in the graph either belongs to D or is adjacent to a vertex in D. The domination number γ(G) is the size of the smallest possible dominating set. This example demonstrates how to:

Find the domination number
Count and enumerate dominating sets
Compute the domination polynomial

We'll explore these concepts using the Petersen graph as our example.

using GenericTensorNetworks, Graphs

Create a Petersen graph instance

graph = Graphs.smallgraph(:petersen)

{10, 15} undirected simple Int64 graph

Define vertex layout for visualization

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)

Tensor Network Formulation

We represent the dominating set problem using tensor networks:

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 problem has two components:

Domination constraints: Every vertex must be dominated
Optimization objective: Minimize the size of the dominating set

constraints(dom)

10-element Vector{ProblemReductions.LocalConstraint}:
 LocalConstraint on [1, 2, 5, 6]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0, 0, 0]  │ false │
│ [1, 0, 0, 0]  │ true  │
│ [0, 1, 0, 0]  │ true  │
│ [1, 1, 0, 0]  │ true  │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ true  │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ true  │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ true  │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ true  │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ true  │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ true  │
└───────────────┴───────┘

 LocalConstraint on [2, 1, 3, 7]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0, 0, 0]  │ false │
│ [1, 0, 0, 0]  │ true  │
│ [0, 1, 0, 0]  │ true  │
│ [1, 1, 0, 0]  │ true  │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ true  │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ true  │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ true  │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ true  │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ true  │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ true  │
└───────────────┴───────┘

 LocalConstraint on [3, 2, 4, 8]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0, 0, 0]  │ false │
│ [1, 0, 0, 0]  │ true  │
│ [0, 1, 0, 0]  │ true  │
│ [1, 1, 0, 0]  │ true  │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ true  │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ true  │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ true  │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ true  │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ true  │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ true  │
└───────────────┴───────┘

 LocalConstraint on [4, 3, 5, 9]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0, 0, 0]  │ false │
│ [1, 0, 0, 0]  │ true  │
│ [0, 1, 0, 0]  │ true  │
│ [1, 1, 0, 0]  │ true  │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ true  │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ true  │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ true  │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ true  │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ true  │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ true  │
└───────────────┴───────┘

 LocalConstraint on [5, 1, 4, 10]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0, 0, 0]  │ false │
│ [1, 0, 0, 0]  │ true  │
│ [0, 1, 0, 0]  │ true  │
│ [1, 1, 0, 0]  │ true  │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ true  │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ true  │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ true  │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ true  │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ true  │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ true  │
└───────────────┴───────┘

 LocalConstraint on [6, 1, 8, 9]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0, 0, 0]  │ false │
│ [1, 0, 0, 0]  │ true  │
│ [0, 1, 0, 0]  │ true  │
│ [1, 1, 0, 0]  │ true  │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ true  │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ true  │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ true  │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ true  │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ true  │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ true  │
└───────────────┴───────┘

 LocalConstraint on [7, 2, 9, 10]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0, 0, 0]  │ false │
│ [1, 0, 0, 0]  │ true  │
│ [0, 1, 0, 0]  │ true  │
│ [1, 1, 0, 0]  │ true  │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ true  │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ true  │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ true  │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ true  │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ true  │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ true  │
└───────────────┴───────┘

 LocalConstraint on [8, 3, 6, 10]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0, 0, 0]  │ false │
│ [1, 0, 0, 0]  │ true  │
│ [0, 1, 0, 0]  │ true  │
│ [1, 1, 0, 0]  │ true  │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ true  │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ true  │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ true  │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ true  │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ true  │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ true  │
└───────────────┴───────┘

 LocalConstraint on [9, 4, 6, 7]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0, 0, 0]  │ false │
│ [1, 0, 0, 0]  │ true  │
│ [0, 1, 0, 0]  │ true  │
│ [1, 1, 0, 0]  │ true  │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ true  │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ true  │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ true  │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ true  │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ true  │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ true  │
└───────────────┴───────┘

 LocalConstraint on [10, 5, 7, 8]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0, 0, 0]  │ false │
│ [1, 0, 0, 0]  │ true  │
│ [0, 1, 0, 0]  │ true  │
│ [1, 1, 0, 0]  │ true  │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ true  │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ true  │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ true  │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ true  │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ true  │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ true  │
└───────────────┴───────┘

objectives(dom)

10-element Vector{ProblemReductions.LocalSolutionSize{Int64}}:
 LocalSolutionSize{Int64} on [1]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [2]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [3]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [4]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [5]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [6]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [7]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [8]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [9]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [10]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

Convert to tensor network representation with optimized contraction order:

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

Mathematical Background

For a graph $G=(V,E)$, we assign a boolean variable $s_v \in \{0,1\}$ to each vertex $v$. The tensor network uses the following components:

Vertex Tensors: For vertex $v$ and its neighbors $N(v)$:
\[T(x_v)_{s_1,...,s_{|N(v)|},s_v} = \begin{cases} 0 & \text{if all } s \text{ values are } 0 \text{ (invalid configuration)} \\ 1 & \text{if } s_v = 0 \text{ (vertex not in set)} \\ x_v^{w_v} & \text{otherwise (vertex in set)} \end{cases}\]

Check the contraction complexity:

contraction_complexity(problem)

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

Solution Analysis

1. Domination Polynomial

The domination polynomial $D(G,x) = \sum_i d_i x^i$ counts dominating sets by size, where $d_i$ is the number of dominating sets of size $i$.

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

10∙x³ + 75∙x⁴ + 192∙x⁵ + 200∙x⁶ + 120∙x⁷ + 45∙x⁸ + 10∙x⁹ + x¹⁰

2. Minimum Dominating Set

Find the domination number γ(G):

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

3.0ₜ

Count minimum dominating sets:

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

(3.0, 10.0)ₜ

3. Configuration Analysis

Enumerate all minimum dominating sets:

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

10-element Vector{StaticBitVector{10, 1}}:
 0100110000
 0010010001
 0001011000
 1001000001
 1010001000
 0101000100
 0000101100
 0100000011
 0010100010
 1000000110

Verify solutions are valid:

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

true

Visualize all minimum dominating sets:

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

Note: For finding just one minimum dominating set, use SingleConfigMin property

More APIs

The Independent Set Problem chapter has more examples on how to use the APIs.

This page was generated using Literate.jl.