Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
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.

We don't have any images related to Partial k-tree yet.
We don't have any YouTube videos related to Partial k-tree yet.
We don't have any PDF documents related to Partial k-tree yet.
We don't have any Books related to Partial k-tree yet.
We don't have any archived web articles related to Partial k-tree yet.

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.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

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.4 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.5

Notes

References

  1. Bodlaender (1988). - 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, vol. 317, Springer-Verlag, pp. 105–118, doi:10.1007/3-540-19488-6_110, hdl:1874/16258, ISBN 978-3-540-19488-0 https://doi.org/10.1007%2F3-540-19488-6_110 ↩

  2. Bodlaender (1998). - 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, hdl:1874/18312 https://doi.org/10.1016%2FS0304-3975%2897%2900228-4 ↩

  3. Arnborg & Proskurowski (1989); Bern, Lawler & Wong (1987); Bodlaender (1988). - 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 https://doi.org/10.1016%2F0166-218X%2889%2990031-0 ↩

  4. Bodlaender (1998). - 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, hdl:1874/18312 https://doi.org/10.1016%2FS0304-3975%2897%2900228-4 ↩

  5. Thorup (1998). - 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 https://doi.org/10.1006%2Finco.1997.2697 ↩