Un árbol k parcial es un tipo de gráfico, ya sea un subgráfico de un árbol k o un gráfico con un ancho de árbol que no exceda k . Muchos problemas combinatorios NP-difíciles en grafos se resuelven en tiempo polinomial, si nos restringimos a k -árboles parciales con algún valor acotado de k .
Para cualquier constante k fija, los árboles k parciales se cierran bajo la operación de tomar grafos menores y, por lo tanto, según el teorema de Robertson-Seymour , dicha familia de grafos puede describirse mediante un conjunto finito de menores prohibidos . Los árboles parciales 1 son exactamente bosques y su único menor prohibido es un triángulo. Para 2 árboles parciales, el único menor prohibido es el gráfico completo de cuatro vértices . Sin embargo, a medida que aumenta el valor de k , aumenta el número de menores prohibidos. Para los 3 árboles parciales, hay cuatro menores prohibidos: el gráfico completo con cinco vértices, el gráfico octaédrico con seis vértices, el gráfico de Wagner con ocho vértices y el gráfico de prisma de cinco puntas con diez vértices [1] .
Muchos problemas algorítmicos que son NP-completos para gráficos arbitrarios se pueden resolver de manera eficiente para k -árboles parciales mediante programación dinámica si se utiliza la descomposición en árbol de estos gráficos [2] [3] [4] .
Si una familia de grafos tiene un ancho de árbol acotado por k , entonces es una subfamilia de k -árboles parciales. Las familias de grafos con esta propiedad incluyen cactus , pseudobosques , grafos secuenciales paralelos, grafos planos exteriores , grafos de Halin y grafos de Apolonio [1] . Por ejemplo, los gráficos secuenciales paralelos son una subfamilia de 2 árboles parciales. Más estrictamente, un gráfico es un 2-árbol parcial si y solo si cualquiera de sus bisagras es paralelo-serie.
Los gráficos de flujo de control que se producen al traducir programas estructurados también tienen un ancho de árbol limitado, lo que permite que algunas tareas, como la asignación de registros , se realicen de manera eficiente [5] .