Coloring problem

Problem definition

A vertex coloring is an assignment of labels or colors to each vertex of a graph such that no edge connects two identically colored vertices. In the following, we are going to defined a 3-coloring problem for 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 define the 3-coloring problem with the Coloring type as

coloring = Coloring{3}(graph)

Coloring{3, 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 3-coloring problem can be obtained by

problem = GenericTensorNetwork(coloring)

GenericTensorNetwork{Coloring{3, Int64, UnitWeight}, OMEinsum.DynamicNestedEinsum{Int64}, Int64}
- open vertices: Int64[]
- fixed vertices: Dict{Int64, Int64}()
- contraction time = 2^10.278, space = 2^6.34, read-write = 2^10.182

Theory (can skip)

Type Coloring can be used for constructing the tensor network with optimized contraction order for a coloring problem. Let us use 3-coloring problem defined on vertices as an example. For a vertex $v$, we define the degrees of freedom $c_v\in\{1,2,3\}$ and a vertex tensor labelled by it as

\[W(v) = \left(\begin{matrix} 1\\ 1\\ 1 \end{matrix}\right).\]

For an edge $(u, v)$, we define an edge tensor as a matrix labelled by $(c_u, c_v)$ to specify the constraint

\[B = \left(\begin{matrix} 1 & x & x\\ x & 1 & x\\ x & x & 1 \end{matrix}\right).\]

The number of possible coloring can be obtained by contracting this tensor network by setting vertex tensor elements $r_v, g_v$ and $b_v$ to 1.

Solving properties

counting all possible coloring

The size of a coloring problem is the number of violations of the coloring constraint.

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

(0.0, 120.0)ₜ

finding one best coloring

single_solution = solve(problem, SingleConfigMin())[]
read_config(single_solution)

is_vertex_coloring(graph, read_config(single_solution))

vertex_color_map = Dict(0=>"red", 1=>"green", 2=>"blue")

show_graph(graph, locations; format=:svg, vertex_colors=[vertex_color_map[Int(c)]
     for c in read_config(single_solution)])

Let us try to solve the same issue on its line graph, a graph that generated by mapping an edge to a vertex and two edges sharing a common vertex will be connected.

linegraph = line_graph(graph)

show_graph(linegraph, [(locations[e.src] .+ locations[e.dst])
     for e in edges(graph)]; format=:svg)

Let us construct the tensor network and see if there are solutions.

lineproblem = Coloring{3}(linegraph);

num_of_coloring = solve(GenericTensorNetwork(lineproblem), CountingMin())[]
read_size_count(num_of_coloring)

17.0 => 1800.0

You will see the maximum size 28 is smaller than the number of edges in the linegraph, meaning no solution for the 3-coloring on edges of a Petersen graph.

This page was generated using Literate.jl.