Partial k-tree
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.
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.[1]
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.[2]
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.[1] 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.[3]
Notes
References
- Arnborg, S.; Proskurowski, A. (1989), "Linear time algorithms for NP-hard problems restricted to partial k-trees", Discrete Applied Mathematics 23 (1): 11–24, doi:10.1016/0166-218X(89)90031-0.
- Bern, M. W.; Lawler, E. L.; Wong, A. L. (1987), "Linear-time computation of optimal subgraphs of decomposable graphs", Journal of Algorithms 8 (2): 216–235, doi:10.1016/0196-6774(87)90039-3.
- Bodlaender, Hans L. (1988), "Dynamic programming on graphs with bounded treewidth", Proc. 15th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 317, Springer-Verlag, pp. 105–118, doi:10.1007/3-540-19488-6_110.
- Bodlaender, Hans L. (1998), "A partial k-arboretum of graphs with bounded treewidth", Theoretical Computer Science 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4.
- Thorup, Mikkel (1998), "All structured programs have small tree width and good register allocation", Information and Computation 142 (2): 159–181, doi:10.1006/inco.1997.2697.