Independent Set Problem
Overview
This example demonstrates how to solve the Independent Set problem using tensor networks. An independent set is a set of vertices in a graph where no two vertices are adjacent. We'll explore this problem using the Petersen graph as our example.
Problem definition
In graph theory, an independent set is a set of vertices in a graph, no two of which are adjacent.
In the following, we are going to solve the solution space properties of the independent set problem on the Petersen graph. To start, let us define a Petersen graph instance.
using GenericTensorNetworks, Graphs
graph = Graphs.smallgraph(:petersen)
{10, 15} undirected simple Int64 graph
We can visualize this graph using the show_graph
function
# set the vertex locations manually instead of using the default spring layout
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)
The graphical display is available in the following editors
Tensor Network Formulation
We represent the independent set problem using a tensor network approach. This allows us to efficiently compute various properties of the solution space.
iset = IndependentSet(graph)
IndependentSet{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 main components:
- Independence constraints: Ensure no adjacent vertices are selected
- Optimization objective: Maximize the size of the independent set
constraints(iset)
15-element Vector{ProblemReductions.LocalConstraint}:
LocalConstraint on [1, 2]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [1, 5]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [1, 6]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [2, 3]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [2, 7]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [3, 4]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [3, 8]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [4, 5]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [4, 9]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [5, 10]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [6, 8]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [6, 9]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [7, 9]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [7, 10]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
LocalConstraint on [8, 10]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0] │ true │
│ [1, 0] │ true │
│ [0, 1] │ true │
│ [1, 1] │ false │
└───────────────┴───────┘
objectives(iset)
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 │
└───────────────┴──────┘
The tensor network representation of the independent set problem can be obtained by
problem = GenericTensorNetwork(iset; optimizer=TreeSA())
GenericTensorNetwork{IndependentSet{SimpleGraph{Int64}, Int64, UnitWeight}, OMEinsum.SlicedEinsum{Int64, OMEinsum.DynamicNestedEinsum{Int64}}, Int64}
- open vertices: Int64[]
- fixed vertices: Dict{Int64, Int64}()
- contraction time = 2^7.977, space = 2^4.0, read-write = 2^8.676
where the key word argument optimizer
specifies the tensor network contraction order optimizer as a local search based optimizer TreeSA
.
Here, the key word argument optimizer
specifies the tensor network contraction order optimizer as a local search based optimizer TreeSA
. The resulting contraction order optimized tensor network is contained in the code
field of problem
.
Mathematical Background
Let $G=(V, E)$ be a graph with each vertex $v\in V$ associated with a weight $w_v$. To reduce the independent set problem on it to a tensor network contraction, we first map a vertex $v\in V$ to a label $s_v \in \{0, 1\}$ of dimension $2$, where we use $0$ ($1$) to denote a vertex absent (present) in the set. For each vertex $v$, we defined a parameterized rank-one tensor indexed by $s_v$ as
\[W(x_v^{w_v}) = \left(\begin{matrix} 1 \\ x_v^{w_v} \end{matrix}\right)\]
where $x_v$ is a variable associated with $v$. Similarly, for each edge $(u, v) \in E$, we define a matrix $B$ indexed by $s_u$ and $s_v$ as
\[B = \left(\begin{matrix} 1 & 1\\ 1 & 0 \end{matrix}\right).\]
Ideally, an optimal contraction order has a space complexity $2^{{\rm tw}(G)}$, where ${\rm tw(G)}$ is the tree-width of $G$ (or graph
in the code). We can check the time, space and read-write complexities by typing
contraction_complexity(problem)
Time complexity: 2^7.977279923499916
Space complexity: 2^4.0
Read-write complexity: 2^8.675957032941747
For more information about how to improve the contraction order, please check the Performance Tips.
Solution Space Analysis
1. Maximum Independent Set Size ($α(G)$)
First, we compute the size of the largest independent set:
maximum_independent_set_size = solve(problem, SizeMax())[]
read_size(maximum_independent_set_size)
4.0
2. Counting Solutions
We can analyze the solution space in several ways:
a. Total Count
Count all possible independent sets:
count_all_independent_sets = solve(problem, CountingAll())[]
76
b. Maximum Solutions
Count independent sets of maximum size:
count_maximum_independent_sets = solve(problem, CountingMax())[]
read_size_count(count_maximum_independent_sets)
4.0 => 5.0
Configuration Analysis
1. Finding Optimal Solutions
We can find a single optimal solution using SingleConfigMax:
max_config = solve(problem, SingleConfigMax(; bounded=false))[]
single_solution = read_config(max_config)
0101010001
Visualize the maximum independent set:
show_graph(graph, locations; format=:svg, vertex_colors=
[iszero(single_solution[i]) ? "white" : "red" for i=1:nv(graph)])
2. Solution Enumeration
We can enumerate all optimal solutions or generate samples:
a. Find all maximum independent sets:
all_max_configs = solve(problem, ConfigsMax(; bounded=true))[]
_, configs_vector = read_size_config(all_max_configs)
4.0 => StaticBitVector{10, 1}[0010111000, 0100100110, 1001001100, 0101010001, 1010000011]
b. Store all independent sets efficiently using a tree structure:
all_independent_sets_tree = solve(problem, ConfigsAll(; tree_storage=true))[]
+ (count = 76.0)
├─ + (count = 58.0)
│ ├─ + (count = 40.0)
│ │ ├─ * (count = 13.0)
│ │ │ ├─ OnehotVec{10, 2}(5, 1)
│ │ │ └─ + (count = 13.0)
│ │ │ ├─ * (count = 1.0)
│ │ │ │ ⋮
│ │ │ │
│ │ │ └─ + (count = 12.0)
│ │ │ ⋮
│ │ │
│ │ └─ + (count = 27.0)
│ │ ├─ * (count = 1.0)
│ │ │ ├─ * (count = 1.0)
│ │ │ │ ⋮
│ │ │ │
│ │ │ └─ * (count = 1.0)
│ │ │ ⋮
│ │ │
│ │ └─ + (count = 26.0)
│ │ ├─ * (count = 4.0)
│ │ │ ⋮
│ │ │
│ │ └─ + (count = 22.0)
│ │ ⋮
│ │
│ └─ * (count = 18.0)
│ ├─ OnehotVec{10, 2}(8, 1)
│ └─ + (count = 18.0)
│ ├─ * (count = 5.0)
│ │ ├─ OnehotVec{10, 2}(5, 1)
│ │ └─ + (count = 5.0)
│ │ ⋮
│ │
│ └─ + (count = 13.0)
│ ├─ * (count = 1.0)
│ │ ⋮
│ │
│ └─ + (count = 12.0)
│ ⋮
│
└─ * (count = 18.0)
├─ OnehotVec{10, 2}(10, 1)
└─ * (count = 18.0)
├─ * (count = 1.0)
│ ├─ OnehotVec{10, 2}(10, 1)
│ └─ OnehotVec{10, 2}(10, 1)
└─ + (count = 18.0)
├─ * (count = 1.0)
│ ├─ * (count = 1.0)
│ │ ⋮
│ │
│ └─ * (count = 1.0)
│ ⋮
│
└─ + (count = 17.0)
├─ * (count = 4.0)
│ ⋮
│
└─ + (count = 13.0)
⋮
Generate a sample of 10 random solutions:
generate_samples(all_independent_sets_tree, 10)
10-element Vector{StaticBitVector{10, 1}}:
0100110000
0100000000
0100010000
0010001000
0100100110
0000101100
0001001100
0001000100
0000000100
0001010001
This page was generated using Literate.jl.