MaxFlow-MinCut Duality for a Paint Shop Problem

Motivated by an application in car manufacturing we consider the following problem: How can we synthesize a given word from restricted reservoirs of colored letters with a minimal number of color changes between adjacent letters? We focus on instances in which each letter occurs exactly twice, once in each of two given colors. In this case the problem turns out to be the dual of a MinCut problem for one point extensions of a certain class of regular matroids. We discuss consequences of the MaxFlow-MinCut duality and describe algorithmic approaches.