zbMATH — the first resource for mathematics

Complexity of finding embeddings in a k-tree. (English) Zbl 0544.68047
TRITA-NA, R. Inst. Technol., Stockh. 8407, 12 p. (1984).
Summary: We address the problem of determining whether a graph is a partial k- tree. We determine the complexity status of two problems related to finding the smallest number k such that a given graph is a partial k- tree. First, finding the minimum such value in NP-hard (the corresponding decision problem is NP-complete). Second, for a fixed (predetermined) value of k, a dynamic programming approach gives algorithms with polynomially bounded (but exponential in k) worst case time complexity. Previously, this problem had only been solved for \(k=1,2,3\).

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity