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.
- Fixed parameter intractability
- Graph problems
- Triangulation of colored graphs
ASJC Scopus subject areas
- Computational Theory and Mathematics