Maximum Cut Problem

Overview

A cut in graph theory divides vertices into two disjoint subsets. The size of a cut is measured by the number of edges (or sum of edge weights) that cross between the subsets. The Maximum Cut (MaxCut) problem seeks to find a cut with the largest possible size.

Key concepts covered:

Finding maximum cuts
Computing cut polynomials
Visualizing cut configurations

This example uses the Petersen graph to demonstrate these concepts.

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 MaxCut problem using tensor networks:

maxcut = MaxCut(graph)

MaxCut{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, 1, 1, 1, 1, 1])

The objective is to maximize the number of edges crossing the cut

objectives(maxcut)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Convert to tensor network representation:

problem = GenericTensorNetwork(maxcut)

GenericTensorNetwork{MaxCut{Int64, UnitWeight}, OMEinsum.DynamicNestedEinsum{Int64}, Int64}
- open vertices: Int64[]
- fixed vertices: Dict{Int64, Int64}()
- contraction time = 2^7.807, space = 2^4.0, read-write = 2^8.379

Mathematical Background

For a graph $G=(V,E)$, we assign a boolean variable $s_v ∈ \{0,1\}$ to each vertex, indicating which subset it belongs to. The tensor network uses:

For edge $(i,j)$ with weight $w_{ij}$:

\[B(x_i, x_j, w_{ij}) = \begin{pmatrix} 1 & x_i^{w_{ij}} \\ x_j^{w_{ij}} & 1 \end{pmatrix}\]

Contributes $x_i^{w_{ij}}$ or $x_j^{w_{ij}}$ when vertices are in different subsets

The contraction complexity is $O(2^{tw(G)})$, where $tw(G)$ is the graph's tree-width.

Solution Analysis

1. Maximum Cut Size

Find the size of the maximum cut:

max_cut_size = solve(problem, SizeMax())[]

12.0ₜ

2. Cut Polynomial

The cut polynomial $C(G,x) = \sum_i c_i x^i$ counts cuts by size, where $c_i/2$ is the number of cuts of size $i$

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

2 + 20∙x³ + 30∙x⁴ + 72∙x⁵ + 200∙x⁶ + 240∙x⁷ + 150∙x⁸ + 120∙x⁹ + 120∙x¹⁰ + 60∙x¹¹ + 10∙x¹²

3. Maximum Cut Configuration

Find one maximum cut solution:

max_vertex_config = read_config(solve(problem, SingleConfigMax())[])

0101010001

Verify the cut size matches our earlier computation:

max_cut_size_verify = cut_size(graph, max_vertex_config)

Visualize the maximum cut:

show_graph(graph, locations; vertex_colors=[
    iszero(max_vertex_config[i]) ? "white" : "red" for i=1:nv(graph)], format=:svg)

Note: Red and white vertices represent the two disjoint subsets of the cut

More APIs

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

This page was generated using Literate.jl.