Maximal independent set problem

Problem definition

In graph theory, a maximal independent set is an independent set that is not a subset of any other independent set. It is different from maximum independent set because it does not require the set to have the max size. In the following, we are going to solve the maximal independent 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 MaximalIS to construct the tensor network for solving the maximal independent set problem as

maximalis = MaximalIS(graph)

MaximalIS{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 maximal independent set problem can be obtained by

problem = GenericTensorNetwork(maximalis)

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

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 its neighborhood $N(v)$:

\[T(x_v)_{s_1,s_2,\ldots,s_{|N(v)|},s_v} = \begin{cases} s_vx_v^{w_v} & s_1=s_2=\ldots=s_{|N(v)|}=0,\\ 1-s_v& \text{otherwise}. \end{cases}\]

The first case corresponds to all the neighborhood vertices of $v$ are not in $I_{m}$, then $v$ must be in $I_{m}$ and contribute a factor $x_{v}^{w_v}$, where $w_v$ is the weight of vertex $v$. Otherwise, if any of the neighboring vertices of $v$ is in $I_{m}$, $v$ must not be in $I_{m}$ by the independence requirement.

Its contraction time space complexity of a MaximalIS instance is no longer determined by the tree-width of the original graph $G$. It is often harder to contract this tensor network than to contract the one for regular independent set problem.

contraction_complexity(problem)

Time complexity: 2^11.129283016944965
Space complexity: 2^9.0
Read-write complexity: 2^11.340406490853294

Solving properties

Counting properties

maximal independence polynomial

The graph polynomial defined for the maximal independent set problem is

\[I_{\rm max}(G, x) = \sum_{k=0}^{\alpha(G)} b_k x^k,\]

where $b_k$ is the number of maximal independent sets of size $k$ in graph $G=(V, E)$.

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

One can see the first several coefficients are 0, because it only counts the maximal independent sets, The minimum maximal independent set size is also known as the independent domination number. It can be computed with the SizeMin property:

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

3.0ₜ

Similarly, we have its counting CountingMin:

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

(3.0, 10.0)ₜ

Configuration properties

finding all maximal independent set

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

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

true

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

This result should be consistent with that given by the Bron Kerbosch algorithm on the complement of Petersen 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]

For sparse graphs, the generic tensor network approach is usually much faster and memory efficient than the Bron Kerbosch algorithm.

finding minimum maximal independent set

It is the ConfigsMin property in the program.

minimum_maximal_configs = solve(problem, ConfigsMin())[].c

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

Similarly, if one is only interested in computing one of the minimum sets, one can use the graph property SingleConfigMin.

This page was generated using Literate.jl.