Vertex Matching Problem

Overview

A k-matching in a graph is a set of k edges where no two edges share a common vertex. A perfect matching occurs when every vertex in the graph is matched. This example demonstrates:

Finding maximum matchings
Computing the matching polynomial
Visualizing matching configurations

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

matching = Matching(graph)

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

Matching constraints: No vertex can be matched more than once
Optimization objective: Maximize the number of matches

constraints(matching)

10-element Vector{ProblemReductions.LocalConstraint}:
 LocalConstraint on [1, 2, 3]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ true  │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ false │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ false │
│   [0, 1, 1]   │ false │
│   [1, 1, 1]   │ false │
└───────────────┴───────┘

 LocalConstraint on [1, 4, 5]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ true  │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ false │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ false │
│   [0, 1, 1]   │ false │
│   [1, 1, 1]   │ false │
└───────────────┴───────┘

 LocalConstraint on [4, 6, 7]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ true  │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ false │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ false │
│   [0, 1, 1]   │ false │
│   [1, 1, 1]   │ false │
└───────────────┴───────┘

 LocalConstraint on [6, 8, 9]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ true  │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ false │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ false │
│   [0, 1, 1]   │ false │
│   [1, 1, 1]   │ false │
└───────────────┴───────┘

 LocalConstraint on [2, 8, 10]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ true  │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ false │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ false │
│   [0, 1, 1]   │ false │
│   [1, 1, 1]   │ false │
└───────────────┴───────┘

 LocalConstraint on [3, 11, 12]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ true  │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ false │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ false │
│   [0, 1, 1]   │ false │
│   [1, 1, 1]   │ false │
└───────────────┴───────┘

 LocalConstraint on [5, 13, 14]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ true  │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ false │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ false │
│   [0, 1, 1]   │ false │
│   [1, 1, 1]   │ false │
└───────────────┴───────┘

 LocalConstraint on [7, 11, 15]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ true  │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ false │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ false │
│   [0, 1, 1]   │ false │
│   [1, 1, 1]   │ false │
└───────────────┴───────┘

 LocalConstraint on [9, 12, 13]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ true  │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ false │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ false │
│   [0, 1, 1]   │ false │
│   [1, 1, 1]   │ false │
└───────────────┴───────┘

 LocalConstraint on [10, 14, 15]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ true  │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ false │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ false │
│   [0, 1, 1]   │ false │
│   [1, 1, 1]   │ false │
└───────────────┴───────┘

objectives(matching)

15-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   │
└───────────────┴──────┘

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

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

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

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

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

Convert to tensor network representation:

problem = GenericTensorNetwork(matching)

GenericTensorNetwork{Matching{Int64, UnitWeight}, OMEinsum.DynamicNestedEinsum{Int64}, Int64}
- open vertices: Int64[]
- fixed vertices: Dict{Int64, Int64}()
- contraction time = 2^9.322, space = 2^5.0, read-write = 2^9.424

Mathematical Background

For a graph $G=(V,E)$, we assign a boolean variable $s_{e} \in \{0,1\}$ to each edge $e$, where $1$ indicates the vertices are matched.

The network uses two types of tensors:

Vertex Tensors: For vertex $v$ with incident edges $e_1,...,e_k$:
\[W_{s_{e₁},...,s_{eₖ}} = \begin{cases} 1 & \text{if } \sum_{i=1}^k s_{e_i} \leq 1\\ 0 & \text{otherwise} \end{cases}\]
This ensures at most one incident edge is selected (at most one match per vertex)
Edge Tensors: For edge $e$:
\[B_{s_e} = \begin{cases} 1 & \text{if } s_e = 0\\ x & \text{if } s_e = 1 \end{cases}\]
This assigns weight $x$ to matched edges and $1$ to unmatched edges

Solution Analysis

1. Maximum Matching

Find the size of the maximum matching:

max_matching = solve(problem, SizeMax())[]
read_size(max_matching)

5.0

Note: A maximum matching size of 5 indicates a perfect matching exists (all vertices are paired)

2. Matching Polynomial

The matching polynomial $M(G,x) = \sum_i c_i x^i$ counts matchings by size, where $c_i$ is the number of $i$-matchings in $G$

matching_poly = solve(problem, GraphPolynomial())[]
read_size_count(matching_poly)

6-element Vector{Pair{Int64, BigInt}}:
 0 => 1
 1 => 15
 2 => 75
 3 => 145
 4 => 90
 5 => 6

3. Perfect Matching Visualization

Find one perfect matching configuration:

match_config = solve(problem, SingleConfigMax())[]
size, config = read_size_config(match_config)

5.0 => 100000110001010

Visualize the matching by highlighting matched edges in red:

show_graph(graph, locations; format=:svg, edge_colors=
    [isone(read_config(match_config)[i]) ? "red" : "black" for i=1:ne(graph)])

Red edges indicate pairs of matched vertices

More APIs

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

This page was generated using Literate.jl.