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

problem = GenericTensorNetwork(coloring)

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

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

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

(15.0, 120.0)ₜ

finding one best coloring

single_solution = solve(problem, SingleConfigMax())[]

is_vertex_coloring(graph, single_solution.c.data)

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 single_solution.c.data])

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, [0.5 .* (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), CountingMax())[]

(28.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.