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:

  1. Independence constraints: Ensure no adjacent vertices are selected
  2. 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.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.977279923499917
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)
1010000011

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}[0100100110, 0010111000, 1010000011, 1001001100, 0101010001]

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)
│  │  │  ├─ + (count = 13.0)
│  │  │  │  ├─ * (count = 1.0)
│  │  │  │  │  ⋮
│  │  │  │  │  
│  │  │  │  └─ + (count = 12.0)
│  │  │  │     ⋮
│  │  │  │     
│  │  │  └─ OnehotVec{10, 2}(5, 1)
│  │  └─ + (count = 27.0)
│  │     ├─ * (count = 1.0)
│  │     │  ├─ * (count = 1.0)
│  │     │  │  ⋮
│  │     │  │  
│  │     │  └─ * (count = 1.0)
│  │     │     ⋮
│  │     │     
│  │     └─ + (count = 26.0)
│  │        ├─ * (count = 4.0)
│  │        │  ⋮
│  │        │  
│  │        └─ + (count = 22.0)
│  │           ⋮
│  │           
│  └─ * (count = 18.0)
│     ├─ + (count = 18.0)
│     │  ├─ * (count = 5.0)
│     │  │  ├─ + (count = 5.0)
│     │  │  │  ⋮
│     │  │  │  
│     │  │  └─ OnehotVec{10, 2}(5, 1)
│     │  └─ + (count = 13.0)
│     │     ├─ * (count = 1.0)
│     │     │  ⋮
│     │     │  
│     │     └─ + (count = 12.0)
│     │        ⋮
│     │        
│     └─ OnehotVec{10, 2}(3, 1)
└─ * (count = 18.0)
   ├─ * (count = 18.0)
   │  ├─ + (count = 18.0)
   │  │  ├─ * (count = 1.0)
   │  │  │  ├─ * (count = 1.0)
   │  │  │  │  ⋮
   │  │  │  │  
   │  │  │  └─ * (count = 1.0)
   │  │  │     ⋮
   │  │  │     
   │  │  └─ + (count = 17.0)
   │  │     ├─ * (count = 4.0)
   │  │     │  ⋮
   │  │     │  
   │  │     └─ + (count = 13.0)
   │  │        ⋮
   │  │        
   │  └─ OnehotVec{10, 2}(4, 1)
   └─ * (count = 1.0)
      ├─ OnehotVec{10, 2}(4, 1)
      └─ OnehotVec{10, 2}(4, 1)

Generate a sample of 10 random solutions:

generate_samples(all_independent_sets_tree, 10)
10-element Vector{StaticBitVector{10, 1}}:
 0100010000
 0100000110
 0000000100
 0100000001
 1000000001
 1010000001
 1010000000
 1010000000
 0001001000
 0001010000

This page was generated using Literate.jl.