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{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 tensor network representation of the matching problem can be obtained by

problem = GenericTensorNetwork(matching)

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

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 => 100001000110100

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.