Partial k-tree
From Wikipedia, the free encyclopedia
In graph theory, a partial k-tree is a type of graph, defined either as a subgraph of a k-tree or as a graph with treewidth at most k.[1] Many NP-hard combinatorial problems on graphs are solvable in polynomial time when restricted to the partial k-trees, for bounded values of k.
For any fixed constant k, the partial k-trees are closed under the operation of graph minors, and therefore, by the Robertson–Seymour theorem, this family can be characterized in terms of a finite set of forbidden minors. The partial 1-trees are exactly the forests, and their single forbidden minor is a triangle. For the partial 2-trees the single forbidden minor is the complete graph on four vertices. However, the number of forbidden minors increases for larger values of k. For partial 3-trees there are four forbidden minors: the complete graph on five vertices, the octahedral graph with six vertices, the eight-vertex Wagner graph, and the pentagonal prism with ten vertices.[2]
Dynamic programming
Many algorithmic problems that are NP-complete for arbitrary graphs may be solved efficiently for partial k-trees by dynamic programming, using the tree decompositions of these graphs.[3]