### Abstract

We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of the letters in the word such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters. This is a special case of the Paint Shop Problem, which was previously shown to be $\mathcal{NP}$-hard. We show that this special case is also $\mathcal{NP}$-hard and even $\mathcal{APX}$-hard

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 7 |

ISBN (Print) | 0169-2690 |

Publication status | Published - 2003 |

### Publication series

Name | Memorandum Afdeling TW |
---|---|

Publisher | Department of Applied Mathematics, University of Twente |

No. | 1681 |

ISSN (Print) | 0169-2690 |

### Keywords

- IR-65866
- METIS-213735
- MSC-68R15
- MSC-90B30
- EWI-3501
- MSC-68Q25

## Cite this

Bonsma, P. S. (2003).

*Complexity results for restricted instances of a paint shop problem*. (Memorandum Afdeling TW; No. 1681). Enschede: University of Twente, Department of Applied Mathematics.