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]

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

This article is issued from Wikipedia - version of the Wednesday, February 20, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.