@article{ef95f34e5dd14437afd2d3ad4425baa0,
title = "The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs",
abstract = "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.",
keywords = "Complexity, Fixed parameter intractability, Graph problems, Triangulation of colored graphs",
author = "Bodlaender, {Hans L.} and Fellows, {Michael R.} and Hallett, {Michael T.} and Wareham, {H. Todd} and Warnow, {Tandy J.}",
note = "Funding Information: (Some of the results contained in this paper were rst reported in H.L. Bodlaender, M.R. Fellows, M.T. Hallett, Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy, in: Proc. 26th Annu. ACM Symp. on the Theory of Computing, 1994, pp. 449{458; H.L. Bodlaender, M.R. Fellows, T.J. Warnow, Two strikes against perfect phylogeny, in: Proc. 19th Internat. Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 623, Springer, Berlin, 1992, pp. 373{383; M.R. Fellows, M.T. Hallett, H.T. Wareham, DNA physical mapping: 3 ways di cult, in: Tom Lengauer (Ed.), Proc. 1st Annu. European Symp. on Algorithms (ESA{\textquoteright}93), Lecture Notes in Computer Science, vol. 726, Springer, Berlin, pp. 157{168. ∗Corresponding author. E-mail address: hansb@cs.uu.nl (H.L. Bodlaender). 1Supported by the ESPRIT Basic Research Actions of the EC under contract 7141 (project ALCOM II). 2Supported by the National Science and Engineering Research Council of Canada. 3This research was done while these authors were at the University of Victoria, Canada. 4Supported in part by a NYI award from the National Science Foundation, CCR-9457800.",
year = "2000",
month = aug,
day = "6",
doi = "10.1016/S0304-3975(98)00342-9",
language = "English (US)",
volume = "244",
pages = "167--188",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1-2",
}