The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
✍ Scribed by Hans L. Bodlaender; Michael R. Fellows; Michael T. Hallett; H.Todd Wareham; Tandy J. Warnow
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 271 KB
- Volume
- 244
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
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, Some of the results contained in this paper were ÿrst reported in H.