Vertex matching problem

Problem definition

A $k$-matching in a graph $G$ is a set of k edges, no two of which have a vertex in common.

using GenericTensorNetworks, Graphs

In the following, we are going to defined a matching problem for the Petersen graph.

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 define the matching problem with the Matching type as

matching = Matching(graph)

Matching{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 matching problem can be obtained by

problem = GenericTensorNetwork(matching)

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

Theory (can skip)

Type Matching can be used for constructing the tensor network with optimized contraction order for a matching problem. We map an edge $(u, v) \in E$ to a label $\langle u, v\rangle \in \{0, 1\}$ in a tensor network, where 1 means two vertices of an edge are matched, 0 means otherwise. Then we define a tensor of rank $d(v) = |N(v)|$ on vertex $v$ such that,

\[W_{\langle v, n_1\rangle, \langle v, n_2 \rangle, \ldots, \langle v, n_{d(v)}\rangle} = \begin{cases} 1, & \sum_{i=1}^{d(v)} \langle v, n_i \rangle \leq 1,\\ 0, & \text{otherwise}, \end{cases}\]

and a tensor of rank 1 on the bond

\[B_{\langle v, w\rangle} = \begin{cases} 1, & \langle v, w \rangle = 0 \\ x, & \langle v, w \rangle = 1, \end{cases}\]

where label $\langle v, w \rangle$ is equivalent to $\langle w,v\rangle$.

Solving properties

The maximum matching size can be obtained by

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

5.0

The largest number of matching is 5, which means we have a perfect matching (vertices are all paired).

The graph polynomial defined for the matching problem is known as the matching polynomial. Here, we adopt the first definition in the wiki page.

\[M(G, x) = \sum\limits_{k=1}^{|V|/2} c_k x^k,\]

where $k$ is the number of matches, and coefficients $c_k$ are the corresponding counting.

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

Configuration properties

one of the perfect matches

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

5.0 => 010011000001001

Let us show the result by coloring the matched edges to red

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

where we use edges with red color to related pairs of matched vertices.

This page was generated using Literate.jl.