a1 ALBCOM Research Group, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Campus Nord, Edifici Omega, C/ Jordi Girona Salgado 1-3, 08034 Barcelona, Spain; firstname.lastname@example.org; email@example.com
This paper studies the computational complexity of the proper interval colored graph problem (PICG), when the input graph is a colored caterpillar, parameterized by hair length. In order prove our result we establish a close relationship between the PICG and a graph layout problem the proper colored layout problem (PCLP). We show a dichotomy: the PICG and the PCLP are NP-complete for colored caterpillars of hair length ≥2, while both problems are in P for colored caterpillars of hair length <2. For the hardness results we provide a reduction from the multiprocessor scheduling problem, while the polynomial time results follow from a characterization in terms of forbidden subgraphs.
(Received February 8 2007)
(Accepted May 14 2009)
(Online publication July 30 2009)
Mathematics Subject Classification: