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
Forbidden minors for partial 3-trees

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]

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
  1. Bodlaender (1998).
  2. Arnborg & Proskurowski (1989); Bern, Lawler & Wong (1987); Bodlaender (1988).
  3. Thorup (1998).
gollark: Incorrect. GTech™ facilities situated in ideatic mathematospace prevent this.
gollark: Secondly, it is not equal; if it were constructible, it would only be isomorphic.
gollark: Firstly, your construction of this set is invalid as I *cannot* be put in sets.
gollark: There are TWO problems with this.
gollark: Proof?

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, ISBN 978-3-540-19488-0.
  • 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.