Binary paint shop problem

Note

It is highly recommended to read the Independent set problem chapter before reading this one.

Problem Definition

The binary paint shop problem is defined as follows: we are given a $2m$ length sequence containing $m$ cars, where each car appears twice. Each car need to be colored red in one occurrence, and blue in the other. We need to choose which occurrence for each car to color with which color — the goal is to minimize the number of times we need to change the current color.

In the following, we use a character to represent a car, and defined a binary paint shop problem as a string that each character appear exactly twice.

using GenericTensorNetworks, Graphs

sequence = collect("iadgbeadfcchghebif")

18-element Vector{Char}:
 'i': ASCII/Unicode U+0069 (category Ll: Letter, lowercase)
 'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
 'd': ASCII/Unicode U+0064 (category Ll: Letter, lowercase)
 'g': ASCII/Unicode U+0067 (category Ll: Letter, lowercase)
 'b': ASCII/Unicode U+0062 (category Ll: Letter, lowercase)
 'e': ASCII/Unicode U+0065 (category Ll: Letter, lowercase)
 'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
 'd': ASCII/Unicode U+0064 (category Ll: Letter, lowercase)
 'f': ASCII/Unicode U+0066 (category Ll: Letter, lowercase)
 'c': ASCII/Unicode U+0063 (category Ll: Letter, lowercase)
 'c': ASCII/Unicode U+0063 (category Ll: Letter, lowercase)
 'h': ASCII/Unicode U+0068 (category Ll: Letter, lowercase)
 'g': ASCII/Unicode U+0067 (category Ll: Letter, lowercase)
 'h': ASCII/Unicode U+0068 (category Ll: Letter, lowercase)
 'e': ASCII/Unicode U+0065 (category Ll: Letter, lowercase)
 'b': ASCII/Unicode U+0062 (category Ll: Letter, lowercase)
 'i': ASCII/Unicode U+0069 (category Ll: Letter, lowercase)
 'f': ASCII/Unicode U+0066 (category Ll: Letter, lowercase)

We can visualize this paint shop problem as a graph

rot(a, b, θ) = cos(θ)*a + sin(θ)*b, cos(θ)*b - sin(θ)*a
locations = [rot(0.0, 100.0, -0.25π - 1.5*π*(i-0.5)/length(sequence)) for i=1:length(sequence)]
graph = path_graph(length(sequence))
for i=1:length(sequence)
    j = findlast(==(sequence[i]), sequence)
    i != j && add_edge!(graph, i, j)
end
show_graph(graph, locations; texts=string.(sequence), format=:svg, edge_colors=
    [sequence[e.src] == sequence[e.dst] ? "blue" : "black" for e in edges(graph)])

Vertices connected by blue edges must have different colors, and the goal becomes a min-cut problem defined on black edges.

Generic tensor network representation

We can define the binary paint shop problem with the PaintShop type as

pshop = PaintShop(sequence)

PaintShop{Char}(['i', 'a', 'd', 'g', 'b', 'e', 'a', 'd', 'f', 'c', 'c', 'h', 'g', 'h', 'e', 'b', 'i', 'f'], Bool[1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0])

The tensor network representation of the binary paint shop problem can be obtained by

problem = GenericTensorNetwork(pshop)

GenericTensorNetwork{PaintShop{Char}, OMEinsum.DynamicNestedEinsum{Char}, Char}(PaintShop{Char}(['i', 'a', 'd', 'g', 'b', 'e', 'a', 'd', 'f', 'c', 'c', 'h', 'g', 'h', 'e', 'b', 'i', 'f'], Bool[1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0]), feg, fge -> 
├─ egfi, gei -> feg
│  ├─ iea, agif -> egfi
│  │  ├─ ia, ea -> iea
│  │  │  ├─ ia
│  │  │  └─ ea
│  │  └─ agf, if -> agif
│  │     ├─ ad, gfd -> agf
│  │     │  ├─ ad, ad -> ad
│  │     │  │  ⋮
│  │     │  │  
│  │     │  └─ dg, df -> gfd
│  │     │     ⋮
│  │     │     
│  │     └─ if
│  └─ gb, eib -> gei
│     ├─ gb
│     └─ be, bi -> eib
│        ├─ be, eb -> be
│        │  ├─ be
│        │  └─ eb
│        └─ bi
└─ fh, geh -> fge
   ├─ fc, hc -> fh
   │  ├─ fc
   │  └─ cc, ch -> hc
   │     ├─ cc
   │     └─ ch
   └─ hg, he -> geh
      ├─ hg, gh -> hg
      │  ├─ hg
      │  └─ gh
      └─ he
, Dict{Char, Int64}())

Theory (can skip)

Type PaintShop can be used for constructing the tensor network with optimized contraction order for solving a binary paint shop problem. To obtain its tensor network representation, we associating car $c_i$ (the $i$-th character in our example) with a degree of freedom $s_{c_i} \in \{0, 1\}$, where we use $0$ to denote the first appearance of a car is colored red and $1$ to denote the first appearance of a car is colored blue. For each black edges $(i, i+1)$, we define an edge tensor labeled by $(s_{c_i}, s_{c_{i+1}})$ as follows: If both cars on this edge are their first or second appearance

\[B^{\rm parallel} = \left(\begin{matrix} x & 1 \\ 1 & x \\ \end{matrix}\right),\]

otherwise,

\[B^{\rm anti-parallel} = \left(\begin{matrix} 1 & x \\ x & 1 \\ \end{matrix}\right).\]

It can be understood as, when both cars are their first appearance, they tend to have the same configuration so that the color is not changed. Otherwise, they tend to have different configuration to keep the color unchanged.

Counting properties

graph polynomial

The graph polynomial defined for the maximal independent set problem is

\[I_{\rm max}(G, x) = \sum_{k=0}^{\alpha(G)} b_k x^k,\]

where $b_k$ is the number of maximal independent sets of size $k$ in graph $G=(V, E)$.

max_config = solve(problem, GraphPolynomial())[]

2∙x⁴ + 28∙x⁵ + 32∙x⁶ + 80∙x⁷ + 60∙x⁸ + 88∙x⁹ + 104∙x¹⁰ + 48∙x¹¹ + 50∙x¹² + 12∙x¹³ + 8∙x¹⁴

Since it only counts the maximal independent sets, the first several coefficients are 0.

Counting properties

graph polynomial

The graph polynomial of the binary paint shop problem in our convention is defined as

\[P(G, x) = \sum_{k=0}^{\delta(G)} p_k x^k\]

where $p_k$ is the number of possible coloring with number of color changes $2m-1-k$.

paint_polynomial = solve(problem, GraphPolynomial())[]

2∙x⁴ + 28∙x⁵ + 32∙x⁶ + 80∙x⁷ + 60∙x⁸ + 88∙x⁹ + 104∙x¹⁰ + 48∙x¹¹ + 50∙x¹² + 12∙x¹³ + 8∙x¹⁴

Configuration properties

finding best solutions

best_configs = solve(problem, ConfigsMin())[]

(4.0, {000000110, 111111001})ₜ

One can see to identical bitstrings corresponding two different vertex configurations, they are related to bit-flip symmetry.

painting1 = paint_shop_coloring_from_config(pshop, best_configs.c.data[1])

show_graph(graph, locations; format=:svg, texts=string.(sequence),
    edge_colors=[sequence[e.src] == sequence[e.dst] ? "blue" : "black" for e in edges(graph)],
    vertex_colors=[isone(c) ? "red" : "black" for c in painting1], config=GraphDisplayConfig(;vertex_text_color="white"))

Since we have different choices of initial color, the number of best solution is 2.

The following function will check the solution and return you the number of color switches

num_paint_shop_color_switch(sequence, painting1)

This page was generated using Literate.jl.