Maximal Independent Set Problem

Overview

A maximal independent set is an independent set that cannot be expanded by including more vertices. Unlike a maximum independent set, it's not necessarily the largest possible independent set.

This example demonstrates:

Finding maximal independent sets
Computing the independence polynomial
Finding minimum maximal independent sets
Comparing with traditional algorithms

We'll explore these concepts using the Petersen graph.

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

Define the maximal independent set problem:

maximalis = MaximalIS(graph)

MaximalIS{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 consists of:

Independence constraints: No adjacent vertices can be selected
Maximality constraints: No more vertices can be added while maintaining independence

constraints(maximalis)

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]  │ false │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ false │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ false │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ false │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ false │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ false │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ false │
└───────────────┴───────┘

 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]  │ false │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ false │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ false │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ false │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ false │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ false │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ false │
└───────────────┴───────┘

 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]  │ false │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ false │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ false │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ false │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ false │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ false │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ false │
└───────────────┴───────┘

 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]  │ false │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ false │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ false │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ false │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ false │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ false │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ false │
└───────────────┴───────┘

 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]  │ false │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ false │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ false │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ false │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ false │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ false │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ false │
└───────────────┴───────┘

 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]  │ false │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ false │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ false │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ false │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ false │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ false │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ false │
└───────────────┴───────┘

 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]  │ false │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ false │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ false │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ false │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ false │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ false │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ false │
└───────────────┴───────┘

 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]  │ false │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ false │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ false │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ false │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ false │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ false │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ false │
└───────────────┴───────┘

 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]  │ false │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ false │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ false │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ false │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ false │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ false │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ false │
└───────────────┴───────┘

 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]  │ false │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ false │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ false │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ false │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ false │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ false │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ false │
└───────────────┴───────┘

objectives(maximalis)

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:

problem = GenericTensorNetwork(maximalis)

GenericTensorNetwork{MaximalIS{Int64, UnitWeight}, OMEinsum.DynamicNestedEinsum{Int64}, Int64}
- open vertices: Int64[]
- fixed vertices: Dict{Int64, Int64}()
- contraction time = 2^11.229, space = 2^9.0, read-write = 2^11.518

Mathematical Background

For a graph $G=(V,E)$, we assign a boolean variable $s_v ∈ \{0,1\}$ to each vertex. For vertex $v$ with neighborhood $N(v)$, we define tensor:

\[T(x_v)_{s_1,...,s_{|N(v)|},s_v} = \begin{cases} s_v x_v^{w_v} & \text{if all neighbors are 0 (v must be included for maximality)} \\ 1-s_v & \text{if any neighbor is 1 (v must be excluded for independence)} \end{cases}\]

Note: This tensor network is often more complex to contract than the regular independent set problem, as its complexity isn't directly tied to the graph's tree-width.

contraction_complexity(problem)

Time complexity: 2^11.228818690495881
Space complexity: 2^9.0
Read-write complexity: 2^11.518161355756956

Solution Analysis

1. Independence Polynomial

The maximal independence polynomial $I_{\text{max}}(G,x) = \sum_i b_i x^i$ counts maximal independent sets by size, where $b_i$ is the number of sets of size $i$

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

10∙x³ + 5∙x⁴

2. Independent Domination Number

Find the size of the smallest maximal independent set:

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

3.0ₜ

Count minimum maximal independent sets:

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

(3.0, 10.0)ₜ

3. Configuration Analysis

Find all maximal independent sets:

maximal_configs = read_config(solve(problem, ConfigsAll())[])

15-element Vector{StaticBitVector{10, 1}}:
 0101000100
 0100110000
 0100100110
 0010100010
 1000000110
 0101010001
 0010010001
 0100000011
 1001000001
 1010000011
 0000101100
 0001011000
 0010111000
 1001001100
 1010001000

Verify solutions are valid:

all(c->is_maximal_independent_set(graph, c), maximal_configs)

true

Visualize all maximal independent sets:

show_configs(graph, locations, reshape(collect(maximal_configs), 3, 5); padding_left=20)

4. Comparison with Classical Algorithms

Compare with Bron-Kerbosch algorithm on complement graph:

cliques = maximal_cliques(complement(graph))

15-element Vector{Vector{Int64}}:
 [5, 6, 7, 3]
 [5, 6, 2]
 [5, 9, 2, 8]
 [5, 9, 3]
 [5, 8, 7]
 [6, 4, 7]
 [6, 4, 2, 10]
 [6, 3, 10]
 [2, 4, 8]
 [2, 9, 10]
 [1, 4, 7, 8]
 [1, 4, 10]
 [1, 9, 10, 3]
 [1, 9, 8]
 [1, 3, 7]

Note: For sparse graphs, our tensor network approach is typically faster and more memory efficient than Bron-Kerbosch.

5. Minimum Maximal Independent Sets

Find all minimum maximal independent sets:

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

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

Visualize minimum maximal independent sets:

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

Note: For finding just one minimum maximal independent set, use the SingleConfigMin property instead

More APIs

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

This page was generated using Literate.jl.