Intervalizing k-colored graphs

Abstract

The problem to determine whether a given k-colored graph is a subgraph of a properly κ-colored interval graph is shown to be solvable in O(n) time when κ = 2, solvable in O(n2) time when κ = 3, and to be NP-complete for any fixed κ ≥ 4. This problem has an application in DNA physical mapping. Our algorithm for κ = 3 is based on an extensive analysis of the precise structure of graphs of pathwidth two, dynamic programming on certain parts of the input graph, and a careful combination of the results for the different parts.