View source for Partial k-tree

{{DISPLAYTITLE:Partial ''k''-tree}}In [[graph theory]], a '''partial ''k''-tree''' is a type of graph, defined either as a subgraph of a [[k-tree|''k''-tree]] or as a graph with [[treewidth]] at most&nbsp;''k''.{{sfnp|Bodlaender|1988}} Many [[NP-hard]] combinatorial problems on graphs are solvable in polynomial time when restricted to the partial ''k''-trees, for bounded values of&nbsp;''k''.

==Graph minors==
[[Image:Partial 3-tree forbidden minors.svg|thumb|Forbidden minors for partial 3-trees]]
For any fixed constant ''k'', the partial ''k''-trees are closed under the operation of [[graph minor]]s, and therefore, by the [[Robertson–Seymour theorem]], this family can be characterized in terms of a finite set of [[forbidden minor]]s. The partial 1-trees are exactly the [[tree (graph theory)|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 [[octahedron|octahedral graph]] with six vertices, the eight-vertex [[Wagner graph]], and the [[pentagonal prism]] with ten vertices.<ref name="b98">{{harvtxt|Bodlaender|1998}}.</ref>

==Dynamic programming==
Many algorithmic problems that are [[NP-completeness|NP-complete]] for arbitrary graphs may be solved efficiently for partial ''k''-trees by [[dynamic programming]], using the [[tree decomposition]]s of these graphs.<ref>{{harvtxt|Arnborg|Proskurowski|1989}}; {{harvtxt|Bern|Lawler|Wong|1987}}; {{harvtxt|Bodlaender|1988}}.</ref>

==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 graph]]s, [[pseudoforest]]s, [[series–parallel graph]]s, [[outerplanar graph]]s, [[Halin graph]]s, and [[Apollonian network]]s.<ref name="b98"/> 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 component]]s is series–parallel.

The [[control-flow graph]]s arising in the [[compiler|compilation]] of [[Structured programming|structured programs]] also have bounded treewidth, which allows certain tasks such as [[register allocation]] to be performed efficiently on them.<ref>{{harvtxt|Thorup|1998}}.</ref>

==Notes==
{{reflist|colwidth=30em}}

==References==
{{refbegin|colwidth=30em}}
*{{citation
 | last1 = Arnborg | first1 = S.
 | last2 = Proskurowski | first2 = A.
 | title = Linear time algorithms for NP-hard problems restricted to partial ''k''-trees
 | journal = Discrete Applied Mathematics
 | volume = 23 | issue = 1 | year = 1989 | pages = 11–24 | doi = 10.1016/0166-218X(89)90031-0| doi-access = free }}.
*{{citation
 | last1 = Bern | first1 = M. W.
 | last2 = Lawler | first2 = E. L. | author2-link = Eugene Lawler
 | last3 = Wong | first3 = A. L.
 | title = Linear-time computation of optimal subgraphs of decomposable graphs
 | journal = Journal of Algorithms
 | volume = 8 | issue = 2 | year = 1987 | pages = 216–235 | doi = 10.1016/0196-6774(87)90039-3}}.
*{{citation
 | last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
 | contribution = Dynamic programming on graphs with bounded treewidth
 | title = Proc. 15th International Colloquium on Automata, Languages and Programming
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | volume = 317 | year = 1988 | pages = 105–118
 | doi = 10.1007/3-540-19488-6_110| hdl = 1874/16258 | isbn = 978-3-540-19488-0 | hdl-access = free}}.
*{{citation
 | last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
 | title = A partial ''k''-arboretum of graphs with bounded treewidth
 | journal = Theoretical Computer Science
 | volume = 209 | issue = 1–2 | pages = 1–45 | year = 1998 | doi = 10.1016/S0304-3975(97)00228-4| hdl = 1874/18312 | hdl-access = free }}.
*{{citation
 | last = Thorup | first = Mikkel | authorlink = Mikkel Thorup
 | title = All structured programs have small tree width and good register allocation
 | journal = Information and Computation
 | volume = 142 | issue = 2 | year = 1998 | pages = 159–181 | doi = 10.1006/inco.1997.2697| doi-access = free }}.
{{refend}}

[[Category:Graph families]]
[[Category:Graph minor theory]]