Draft:Binary Paint shop problem

Binary Paintshop problem

Description

The binary paintshop problem is an operations research problem. Its description is simple, but finding an optimal solution can be difficult.

Let $n\geq 1$ be an integer, and let the alphabet contain $n$ characters. The input is a word of length $2n$ in which each character appears exactly twice. Color the two occurrences of each character differently: one blue and one red.

The goal is to color the word while minimizing the number of color changes between adjacent letters.

For example, if $n=3$, the alphabet is $\{a,b,c\}$, and the word is abacbc. One possible coloring, in order, is blue, red, red, red, blue, blue. It has two color changes, which is the minimum for this example.

A presentation of the problem can be found in this paper.

The binary paintshop problem is a special case of a more general problem in which letters may appear different numbers of times and more than two colors may be used. In that general problem, no two occurrences of the same letter may receive the same color.

History

This problem comes from the early age of car factory. At the time, changing the painting color was an expensive and long part of the production. Therefore in the production line, one goal was to reduce the amount of changes, though it was possible to invert some of the models, this being complicated we restrain the possibility to have an easy modelisation.

Computational complexity

Brute-force algorithm

Each character has two possible assignments of blue and red to its two occurrences. Thus, there are $2^{n}$ possible colorings to consider. Given one such coloring, we can check its validity and count its color changes in $O(n)$ time. Exhaustive search therefore takes $O(n2^{n})$ time.

NP and certificates

A decision problem is in the class NP if every “yes” instance has a certificate of polynomial length that a deterministic algorithm can verify in polynomial time.

The decision version of the binary paintshop problem asks:

Given a word and an integer $k$, is there a valid coloring with at most $k$ color changes?

A certificate is a coloring of the word. To verify it, check that the two occurrences of each character have different colors, then count the color changes and check that their number is at most $k$. If the letters are indexed by an array, this takes time linear in the word length. Therefore, the decision problem is in NP.

An equivalent definition is that a decision problem is in NP if a non-deterministic Turing machine can decide it in polynomial time.

Why the two definitions of NP are equivalent

Suppose a non-deterministic Turing machine decides a problem in polynomial time. A certificate can describe one accepting computation path, including its states, transitions, and nondeterministic choices. The path has polynomial length. A deterministic verifier can check, step by step, that each transition is legal and that the path ends in an accepting state.

Conversely, suppose every “yes” instance $u$ has a certificate $x$ of polynomial length that a deterministic verifier can check in polynomial time. A non-deterministic Turing machine can guess $x$ and run the verifier on $(u,x)$. It accepts exactly when the verifier accepts. The machine runs in polynomial time and accepts $u$ if and only if a valid certificate exists.

NP-hardness and NP-completeness

A decision problem is NP-hard if every problem in NP can be reduced to it in polynomial time. In particular, a polynomial-time algorithm for an NP-hard problem would give a polynomial-time algorithm for every problem in NP.

A problem that is both NP-hard and in NP is called NP-complete.

The Cook–Levin theorem establishes that Boolean satisfiability (SAT) is NP-complete. The proof below outlines the tableau construction.

Cook–Levin theorem

A SAT instance is a Boolean formula. The question is whether there is an assignment of truth values to its variables that makes the formula true. SAT is in NP because a truth assignment is a certificate that can be checked in polynomial time.

To show that SAT is NP-hard, take any decision problem $L$ in NP. There is a non-deterministic Turing machine $M$ that decides $L$ in polynomial time. We construct, for each input word $u$, a Boolean formula that is satisfiable if and only if $M$ accepts $u$. Encoding the computation

Let $n$ be the length of $u$, and let $P=p(n)$ be a polynomial bound on the number of steps taken by $M$. We may assume that an accepting computation can be extended to exactly $P$ steps by giving accepting states transitions that leave the configuration unchanged.

Use a one-tape machine whose head moves at most one cell per step. The input is written in cells $0,\ldots ,n-1$, and the head starts at cell $0$. During $P$ steps, the head cannot leave the tape interval

$I=\{-P,-P+1,\ldots ,n+P\}.$

The formula describes a computation table. Each row is a time step; the entries record the machine state, head position, and tape contents. Introduce Boolean variables:

• $T_{t,i,a}$ is true if tape cell $i$ contains symbol $a$ at time $t$.
• $H_{t,i}$ is true if the head is at cell $i$ at time $t$.
• $Q_{t,q}$ is true if the machine is in state $q$ at time $t$.

Here, $0\leq t\leq P$, $i\in I$, $a$ belongs to the fixed tape alphabet $\Gamma$, and $q$ belongs to the fixed state set $Q$. Since $|I|=O(n+P)$ and $Q$ and $\Gamma$ are fixed for $M$, the number of variables is polynomial in $n$. Valid configurations

At each time, exactly one state is active:

$\left(\bigvee _{q\in Q}Q_{t,q}\right)\land \bigwedge _{q\in Q}\bigwedge _{q'\in Q,\ q'\neq q}(\neg Q_{t,q}\lor \neg Q_{t,q'}).$

At each time, the head is in exactly one position:

$\left(\bigvee _{i\in I}H_{t,i}\right)\land \bigwedge _{i\in I}\bigwedge _{i'\in I,\ i'\neq i}(\neg H_{t,i}\lor \neg H_{t,i'}).$

For every time and tape cell, exactly one tape symbol is present:

$\left(\bigvee _{a\in \Gamma }T_{t,i,a}\right)\land \bigwedge _{a\in \Gamma }\bigwedge _{a'\in \Gamma ,\ a'\neq a}(\neg T_{t,i,a}\lor \neg T_{t,i,a'}).$

Initial configuration

Let $s$ be the start state, and let $\sqcup$ denote the blank symbol. The initial state and head position are specified by

$Q_{0,s}\land H_{0,0}.$

For each input position $i$, set the corresponding tape cell to the input symbol $u_{i}$:

$\bigwedge _{0\leq i<n}T_{0,i,u_{i}}.$

All other cells in $I=\{-P,\ldots ,n+P\}$ start blank:

$\left(\bigwedge _{-P\leq i<0}T_{0,i,\sqcup }\right)\land \left(\bigwedge _{n\leq i\leq n+P}T_{0,i,\sqcup }\right).$

Legal transitions

Write a transition as $\tau =(q,a,q',a',d)$. For each $i$, let $\delta _{i}(q,a)$ be the set of allowed transitions from state $q$ reading $a$ whose destination cell $i+d$ belongs to $I$.

For each time $t<P$, position $i\in I$, state $q$, and symbol $a\in \Gamma$, require that if the machine is in state $q$ at $i$ and reads $a$, one of the allowed transitions occurs:

$Q_{t,q}\land H_{t,i}\land T_{t,i,a}\;\Rightarrow \;\bigvee _{\tau =(q,a,q',a',d)\in \delta _{i}(q,a)}\left(Q_{t+1,q'}\land H_{t+1,i+d}\land T_{t+1,i,a'}\land \bigwedge _{j\in I,\ j\neq i}\bigwedge _{b\in \Gamma }(T_{t,j,b}\leftrightarrow T_{t+1,j,b})\right).$

The last conjunction requires every tape cell other than the one under the head to keep its symbol. The disjunction represents the machine's nondeterministic choices. If no transition is available for the current state and symbol, the disjunction is false.

Acceptance

Let $F\subseteq Q$ be the set of accepting states. Require the machine to be in an accepting state at time $P$:

$\bigvee _{q\in F}Q_{P,q}.$

The formula has polynomial size. There are polynomially many time steps and tape cells, and the state set, tape alphabet, and transition relation are fixed for $M$. Even the transition constraints, which can refer to every tape cell, have polynomial total size. The formula can be constructed in polynomial time. If SAT is expressed using conjunctive normal form, the formula can be converted to an equisatisfiable CNF formula of polynomial size using auxiliary variables.

Correctness

If $M$ has an accepting computation on $u$, its configurations give values to the variables that satisfy the formula. Conversely, any satisfying assignment describes a valid sequence of configurations of $M$ on $u$ ending in an accepting state. Thus the formula is satisfiable if and only if $M$ accepts $u$.

Therefore, every problem in NP reduces to SAT in polynomial time. SAT is NP-hard and is also in NP, so it is NP-complete.

APX, PTAS, and APX-hardness

These definitions concern optimization problems. Assume that feasible solutions can be represented and checked in polynomial time and that their objective values can be computed in polynomial time.

For a minimization problem, an algorithm is a $c$-approximation if it returns a feasible solution of cost at most $c\operatorname {OPT}$, where $\operatorname {OPT}$ is the minimum possible cost and $c\geq 1$. For a maximization problem, it is a $c$-approximation if it returns a feasible solution of value at least $\operatorname {OPT} /c$.

APX

The class APX consists of the optimization problems that have a polynomial-time approximation algorithm with some fixed constant approximation factor.

PTAS

A polynomial-time approximation scheme (PTAS) is a family of algorithms with the following guarantee: for every fixed $c>1$, there is a polynomial-time algorithm that returns a $c$-approximation. The degree of the running-time polynomial may depend on $c$.

PTAS reduction

A PTAS reduction transforms instances and solutions of one optimization problem into instances and solutions of another while preserving arbitrarily accurate approximation.

A problem $A$ PTAS-reduces to a problem $B$ if, for every $\varepsilon >0$, there are polynomial-time procedures (for fixed $\varepsilon$) and a value $\delta (\varepsilon )>0$ such that:

1. An instance $x$ of $A$ is transformed into an instance $y$ of $B$.
2. Any $(1+\delta (\varepsilon ))$-approximate solution to $y$ can be transformed into a $(1+\varepsilon )$-approximate solution to $x$.

The reduction may choose the target accuracy $\delta$ as a function of the desired source accuracy $\varepsilon$.

APX-hardness

An optimization problem $B$ is APX-hard if every problem in APX PTAS-reduces to $B$. If $B$ had a PTAS, then every problem in APX would have a PTAS. Under the standard assumption $P\neq NP$, APX-hard problems therefore have no PTAS.

A problem is APX-complete if it is both APX-hard and in APX. APX-hardness is a stronger approximation-hardness result than NP-hardness.

NP-hardness of the binary paintshop problem

Bonsma, Epping, and Hochstättler proved that the decision version of the binary paintshop problem is NP-complete and that its optimization version is APX-hard. The proof below gives the reduction from vertex cover on cubic graphs.

Orientation lemma

The reduction uses an ordering and orientation of the edges of a graph.

Lemma. Every simple graph $H=(V,F)$ of maximum degree at most 3 has a total vertex order $\prec$ and an orientation of its edges such that:

1. Each vertex has at most one incoming arc from a vertex earlier in the order and at most one incoming arc from a vertex later in the order.
2. Every vertex of degree 2 has exactly one incoming arc.

The order and orientation can be found in polynomial time.

Proof. We use induction on $|V|$. If $H$ is disconnected, apply the induction hypothesis to each connected component and concatenate their orders. Since there are no edges between components, the in-neighbors and their relative order within each component are unchanged. It therefore suffices to consider connected graphs.

The result is immediate for a graph with one vertex. For a larger connected graph, consider the following cases.

1. $H$ has a vertex of degree 1

Let $v$ be a leaf with neighbor $u$. Apply induction to $H-v$.

If $u$ has degree 1 in $H$, then $H$ consists of the edge $uv$, which can be oriented arbitrarily.

If $u$ has degree 2 in $H$, it has degree 1 in $H-v$. If its existing edge is directed into $u$, orient the new edge as $u\to v$. Otherwise, orient it as $v\to u$. In either case, $u$ has exactly one incoming arc.

If $u$ has degree 3 in $H$, it has degree 2 in $H-v$ and already has exactly one incoming arc. Orient the new edge as $u\to v$ and place $v$ last in the order. This does not add an incoming arc to $u$.

In each case, the conditions are preserved.

2. $H$ has a degree-2 vertex $v$ with neighbors $u,w$, where $uw\notin F$

Form $H'=(H-v)+uw$. Apply induction to $H'$. Relabel $u,w$ if necessary so that $u\prec w$. Replace the oriented edge between $u$ and $w$ with a directed path through $v$, and insert $v$ between $u$ and $w$. For example, replace $u\to w$ by $u\to v\to w$, or replace $w\to u$ by $w\to v\to u$.

The direction and relative order of the corresponding edge at each of $u$ and $w$ are preserved. The new degree-2 vertex $v$ has exactly one incoming arc.

3. $H$ has a degree-2 vertex $v$ with neighbors $u,w$, where $uw\in F$

Apply induction to $H-v$. Rename $u,w$ so that the existing edge is oriented $u\to w$. The degree of $u$ in $H-v$ is at most 2, so it has at most one incoming neighbor; call it $x$, if it has one.

Add the arcs $w\to v$ and $v\to u$. If $x$ exists and $x\prec u$, insert $v$ immediately after $u$. Otherwise, insert $v$ immediately before $u$. The new incoming neighbor $v$ is on the opposite side of $u$ from $x$, if $x$ exists. Thus $u$ has at most one incoming neighbor on either side. The incoming neighbors of $w$ are unchanged, and $v$ has exactly one incoming arc, from $w$. The conditions are preserved.

4. Every vertex of $H$ has degree 3

Choose a vertex $v$ and apply induction to $H-v$. Its three neighbors $x,y,z$ have degree 2 in $H-v$, so each has exactly one incoming neighbor there.

For each of $x,y,z$, that incoming neighbor is either earlier or later in the order. By the pigeonhole principle, at least two of the three vertices have the same relation. Name those two $x,y$, and name their incoming neighbors $u,w$. Thus either $u\prec x$ and $w\prec y$, or $x\prec u$ and $y\prec w$.

In the first case, insert $v$ after both $x$ and $y$; in the second case, insert it before both. Add the arcs $v\to x$, $v\to y$, and $z\to v$. Each of $x$ and $y$ now has two incoming neighbors, one on either side in the order. The incoming neighbors of $z$ are unchanged, and $v$ has exactly one incoming arc.

This proves the lemma. The induction makes at most a polynomial number of graph modifications and order operations, so the ordering and orientation can be found in polynomial time. $\square$

The reduction

Take an instance $(G,k)$ of vertex cover on cubic graphs, where $G=(V,F)$ and $|V|=n$. Apply the orientation lemma and renumber the vertices so that $V=\{1,\ldots ,n\}$ and $i\prec j$ exactly when $i<j$.

At each vertex $i$, order its three incident arcs as $a_{i,1},a_{i,2},a_{i,3}$ as follows:

• If an arc $a=(p,i)$ enters $i$ from an earlier vertex, place it first.
• If an arc $a=(p,i)$ enters $i$ from a later vertex, place it last.
• Place any remaining incident arcs in the remaining positions.

The orientation lemma guarantees that these instructions do not conflict: there is at most one incoming arc from an earlier vertex and at most one from a later vertex. Write $E_{a}$ for the letter associated with arc $a$.

Create the letters $A_{i},B_{i},C_{i}$ for each vertex $i$, the letter $E_{a}$ for each arc $a$, and the letter $D_{ij}$ for each pair of vertices with $i<j$. Define the block for vertex $i$ by

$W_{i}=A_{i}\,D_{1i}D_{2i}\cdots D_{i-1,i}\,E_{a_{i,1}}E_{a_{i,2}}E_{a_{i,3}}\,B_{i}B_{i}\,D_{i,i+1}D_{i,i+2}\cdots D_{i,n}\,A_{i}C_{i}C_{i}.$

An empty sequence of $D$-letters is omitted. The constructed word is

$w=W_{1}W_{2}\cdots W_{n}.$

Every letter appears exactly twice. Each $A_{i},B_{i},C_{i}$ appears twice in $W_{i}$; each $E_{a}$ appears once in the blocks of the two endpoints of arc $a$; and each $D_{ij}$ appears once in $W_{i}$ and once in $W_{j}$. Thus $w$ is a valid binary paintshop instance. It has length $n^{2}+8n$, so the construction takes polynomial time.

Correctness

For a coloring, call a gap between adjacent letters a change if the colors on the two sides differ. For a letter $X$, let $I_{X}$ be the interval between its two occurrences. The coloring is valid if and only if every $I_{X}$ contains an odd number of changes: traversing an odd number of changes switches the color, while an even number leaves it unchanged.

Let $\tau (G)$ be the minimum size of a vertex cover in $G$. We prove that

$\operatorname {OPT} (w)=2n+2\tau (G).$

Lower bound

Consider any valid coloring, and let $c_{i}$ be the number of changes strictly inside block $W_{i}$, not counting a gap between consecutive blocks. The adjacent pairs $B_{i}B_{i}$ and $C_{i}C_{i}$ each force a change, so $c_{i}\geq 2$.

Suppose $c_{i}\leq 3$. The interval $I_{A_{i}}$ contains the change between $B_{i}B_{i}$ and must contain an odd number of changes. There can be at most one other change in the block. It follows that $I_{A_{i}}$ contains exactly one change: the one between $B_{i}B_{i}$.

Now consider an edge $\{i,j\}\in F$ with $i<j$, and let $a$ be its oriented arc. In block $W_{i}$, $E_{a}$ occurs before $B_{i}B_{i}$, while $D_{ij}$ occurs after it. If $c_{i}\leq 3$, there is exactly one change between these occurrences of $E_{a}$ and $D_{ij}$. In block $W_{j}$, both $D_{ij}$ and $E_{a}$ occur before $B_{j}B_{j}$. If $c_{j}\leq 3$, there are no changes between them: the only change inside $I_{A_{j}}$ is the one at $B_{j}B_{j}$, which comes after both letters.

The intervals $I_{E_{a}}$ and $I_{D_{ij}}$ share the part between the occurrence of $D_{ij}$ in $W_{i}$ and its occurrence in $W_{j}$. The parts in which they differ are precisely the segment from $E_{a}$ to $D_{ij}$ in $W_{i}$ and the segment from $D_{ij}$ to $E_{a}$ in $W_{j}$. Together these segments contain an odd number of changes: one in $W_{i}$ and none in $W_{j}$. Therefore $I_{E_{a}}$ and $I_{D_{ij}}$ have opposite parities, contradicting validity, which requires both to have odd parity.

Consequently, for every edge $\{i,j\}$, at least one of $c_{i},c_{j}$ is at least 4. The set

$S'=\{i\in V:c_{i}\geq 4\}$

is therefore a vertex cover. Every block has at least two changes, and each block indexed by $S'$ has at least two additional changes. Hence the total number of changes, including any changes between blocks, is at least

$\sum _{i=1}^{n}c_{i}\geq 2n+2|S'|\geq 2n+2\tau (G).$

Thus $\operatorname {OPT} (w)\geq 2n+2\tau (G)$.

Upper bound

Let $S$ be a vertex cover of $G$. We specify gaps at which to change color. Start the word blue and toggle the color at each specified gap.

In every block $W_{i}$, place changes in the gaps $B_{i}\mid B_{i}$ and $C_{i}\mid C_{i}$. If $i\in S$, also place two changes:

• $L_{i}$, immediately before the first of the three $E$-letters. This is the gap between the last $D$-letter in the prefix and the first $E$-letter. If there is no $D$-letter in the prefix, use the gap between the first $A_{i}$ and the first $E$-letter.
• $R_{i}$, immediately after the last $E$-letter and before the first $B_{i}$.

For an edge whose endpoints are both in $S$, shift one of these additional changes:

• If $a=(i,j)$ with $i<j$, then $E_{a}$ is first among the $E$-letters in $W_{j}$. Move $L_{j}$ one gap to the right, immediately after $E_{a}$.
• If $a=(j,i)$ with $i<j$, then $E_{a}$ is last among the $E$-letters in $W_{i}$. Move $R_{i}$ one gap to the left, immediately before $E_{a}$.

The ordering of incident arcs ensures that the specified letters are adjacent. The orientation lemma also ensures that at most one incoming arc from an earlier vertex and at most one from a later vertex can cause a shift at any vertex. Thus the prescribed gaps are distinct.

We check that every pair of equal letters has an odd number of changes between its occurrences.

• Each of $B_{i}$ and $C_{i}$ has exactly one change between its adjacent occurrences.
• The interval $I_{A_{i}}$ contains the change at $B_{i}\mid B_{i}$. If $i\in S$, it also contains $L_{i}$ and $R_{i}$. It therefore contains either one or three changes.
• For $D_{ij}$, where $i<j$, the interval between its occurrences contains the change at $C_{i}\mid C_{i}$. It contains no changes in the prefix of $W_{j}$ before $D_{ij}$. Any complete blocks between $W_{i}$ and $W_{j}$ contain either two or four changes, and there are no changes between blocks. Thus $I_{D_{ij}}$ contains an odd number of changes.
• For an edge $\{i,j\}$, where $i<j$, compare $I_{E_{a}}$ and $I_{D_{ij}}$. The parts in which these intervals differ are the segment from $E_{a}$ to $D_{ij}$ in $W_{i}$ and the segment from $D_{ij}$ to $E_{a}$ in $W_{j}$. The first contains the change at $B_{i}\mid B_{i}$. Since $S$ is a vertex cover, at least one endpoint of the edge belongs to $S$. The placement and shifting rules ensure that exactly one additional change, either $R_{i}$ or $L_{j}$, lies in these two segments. If both endpoints are in $S$, the change at the head of the arc is shifted out of its segment, leaving the change at the other endpoint inside. The ordering of the incident arcs ensures that shifts made for other edges do not remove this remaining change. The two differing segments therefore contain an even number of changes: the change at $B_{i}\mid B_{i}$ and exactly one additional change. It follows that $I_{E_{a}}$ and $I_{D_{ij}}$ have the same parity. Since $I_{D_{ij}}$ has odd parity, so does $I_{E_{a}}$.

The specified changes therefore give a valid coloring. Each block has exactly two changes if $i\notin S$ and exactly four if $i\in S$. In either case, the number of changes in the block is even, so every block ends in the same color in which it began. There are no changes between blocks. The total number of changes is $2n+2|S|$.

Taking $S$ to be a minimum vertex cover gives $\operatorname {OPT} (w)\leq 2n+2\tau (G)$. Together with the lower bound, this proves

$\operatorname {OPT} (w)=2n+2\tau (G).$

Conclusion

Map the cubic vertex-cover instance $(G,k)$ to the word $w$ constructed above and the paintshop threshold

$K=2n+2k.$

The optimum-value equality gives

$G{\text{ has a vertex cover of size at most }}k\quad \Longleftrightarrow \quad w{\text{ has a valid coloring with at most }}K{\text{ changes}}.$

The construction is polynomial-time, so it is a polynomial-time many-one reduction. The decision version of the binary paintshop problem is therefore NP-hard. Since it is also in NP, it is NP-complete. The same paper proves the stronger result that the optimization problem is APX-hard.

APX-hardness of the binary paint shop problem

APX-hardness

Minimum vertex cover on cubic graphs is APX-hard. We use the same reduction as before.

Let $G=(V,F)$ be a cubic graph, let $n=|V|$, and let $\tau (G)$ be the size of a minimum vertex cover. Construct the corresponding binary paintshop word as in the previous section. Its optimum number of color changes is

$$\operatorname {OPT} _{\mathrm {paint} }=2n+2\tau (G).$$ Suppose there is a PTAS for the binary paintshop problem. For any $\varepsilon >0$, apply it to the constructed word and let $C$ be the number of changes in the coloring it returns. Then

$$C\leq (1+\varepsilon ){\bigl (}2n+2\tau (G){\bigr )}.$$

Let $c_{i}$ be the number of changes inside block $i$, excluding any change between blocks. As shown in the previous section, the vertices whose blocks have at least four changes form a vertex cover. Let

$$S_{\mathrm {approx} }=\{i\in V:c_{i}\geq 4\},\qquad b=|S_{\mathrm {approx} }|.$$

Each block has at least two changes. Each block in $S_{\mathrm {approx} }$ has at least two additional changes. Changes between blocks can only add to the total, so

$$C\geq \sum _{i\in V}c_{i}\geq 2(n-b)+4b=2n+2b.$$

Therefore, $S_{\mathrm {approx} }$ is a vertex cover and

$${\begin{aligned}b&\leq {\frac {C-2n}{2}}\\&\leq \varepsilon n+(1+\varepsilon )\tau (G).\end{aligned}}$$

A cubic graph has $3n/2$ edges, and each vertex covers at most three edges. Thus every vertex cover has size at least

$$\tau (G)\geq {\frac {|F|}{3}}={\frac {n}{2}},\qquad {\text{so}}\qquad n\leq 2\tau (G).$$

It follows that

$$b\leq \varepsilon n+(1+\varepsilon )\tau (G)\leq (1+3\varepsilon )\tau (G).$$

Thus, a $(1+\varepsilon )$-approximation for the binary paintshop problem gives a $(1+3\varepsilon )$-approximation for minimum vertex cover on cubic graphs. By choosing $\varepsilon$ appropriately, a PTAS for the binary paintshop problem would give a PTAS for cubic vertex cover.

Since minimum vertex cover on cubic graphs is APX-hard, this approximation-preserving reduction shows that the binary paintshop optimization problem is APX-hard.

Complexity under unique game conjecture

Under [Unique games conjecture], as one can reduce min uncut problem to binary paint shop problem, one can show that, there is no constant approximation algorithm in polynomial time for the binary paint shop problem. Therefore one can only hope to use heuristic that holds on most instances, or that hold in probability assuming uniform distribution of words.

Algorithms

As the problem is NP Hard, searching a polynomial time algorithm would be a loose of time, but there exist some approximation algorithms.