Anupam Gupta, Satyen Kale, Viswanath Nagarajan, Rishi Saket, and Baruch Schieber
Proceedings of 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2013

In the Binary Paintshop problem, there are $$m$$ cars appearing in a sequence of length $$2m$$, with each car occurring twice. Each car needs to be colored with two colors. The goal is to choose for each car, which of its occurrences receives either color, so as to minimize the total number of color changes in the sequence. We show that the Binary Paintshop problem is equivalent (up to constant factors) to the Minimum Uncut problem, under randomized reductions. By derandomizing this reduction for hard instances of the Minimun Uncut problem arising from the Unique Games Conjecture, we show that the Binary Paintshop problem is $$\omega(1)$$-hard to approximate (assuming the UGC). This answers an open question from Eppinger et al (2006), Meunier and Sebo (2009) and Andres and Hochstattler (2011).