It should be noted that performance guarantees provided by most of our approximation algorithms are constants, independent of the size of the input graph. For the reader s convenience, the de nition of treewidth and the associated concepts are included in the appendix. The Constructive Approach from Predicates. This would be significant in making the theoretically interesting linear time graph algorithms be practically useful. We give a definition of tree decompositions below.
Many intractable problems are solvable in polynomial time for partial k trees.
For the proof of this it is used that the chromatic number of a partial k tree is at most k 1. A similar approach is useful to get a linear algorithm for PrExt with a fixed number of colors. For the precise definition, see Section 2. Much research has been done on the problem of determining the treewidth and the pathwidth of a graph, and finding optimal tree or path decompositions with optimal treewidth or pathwidth. From this it follows that also our problem of finding optimal t spanners is NP complete.