The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs

Hans L. Bodlaender, Michael R. Fellows, Michael T. Hallett, H. Todd Wareham, Tandy J. Warnow

Research output: Contribution to journalArticle


In this paper, we consider the complexity of a number of combinatorial problems; namely, INTERVALIZING COLORED GRAPHS (DNA PHYSICAL MAPPING), TRIANGULATING COLORED GRAPHS (PERFECT PHYLOGENY), (DIRECTED) (MODIFIED) COLORED CUTWIDTH, FEASIBLE REGISTER ASSIGNMENT and MODULE ALLOCATION FOR GRAPHS OF BOUNDED PATHWIDTH. Each of these problems has as a characteristic a uniform upper bound on the tree or path width of the graphs in "yes"-instances. For all of these problems with the exceptions of FEASIBLE REGISTER ASSIGNMENT and MODULE ALLOCATION, a vertex or edge coloring is given as part of the input. Our main results are that the parameterized variant of each of the considered problems is hard for the complexity classes W[t] for all t ∈ N. We also show that INTERVALIZING COLORED GRAPHS, TRIANGULATING COLORED GRAPHS, and COLORED CUTWIDTH are NP-Complete.

Original languageEnglish (US)
Pages (from-to)167-188
Number of pages22
JournalTheoretical Computer Science
Issue number1-2
StatePublished - Aug 6 2000



  • Complexity
  • Fixed parameter intractability
  • Graph problems
  • Triangulation of colored graphs

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Cite this