 | ||
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. Many NP-hard combinatorial problems on graphs are solvable in polynomial time when restricted to the partial k-trees, for bounded values of k.
Contents
Graph minors
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.
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.
Related families of graphs
If a family of graphs has bounded treewidth, then it is a subfamily of the partial k-trees, where k is the bound on the treewidth. Families of graphs with this property include the cactus graphs, pseudoforests, series-parallel graphs, outerplanar graphs, Halin graphs, and Apollonian networks. For instance, the series-parallel graphs are a subfamily of the partial 2-trees, and more strongly a graph is a partial 2-tree if and only if each of its biconnected components is series-parallel.
The control flow graphs arising in the compilation of structured programs also have bounded treewidth, which allows certain tasks such as register allocation to be performed efficiently on them.