k -árbol parcial

En teoría de grafos , un k -árbol parcial es un tipo de grafo, definido como un subgrafo de un k- árbol o como un grafo con un ancho de árbol como máximo k . ^{[ 1 ]} Muchos problemas combinatorios NP-difíciles en grafos son resolubles en tiempo polinomial cuando se restringen a los k- árboles parciales, para valores acotados de k .  

Para cualquier constante k fija , los k- árboles parciales son cerrados bajo la operación de menores de grafos y, por lo tanto, según el teorema de Robertson-Seymour , esta familia puede caracterizarse en términos de un conjunto finito de menores prohibidos . Los 1-árboles parciales son precisamente los bosques , y su único menor prohibido es un triángulo. Para los 2-árboles parciales, el único menor prohibido es el grafo completo de cuatro vértices. Sin embargo, el número de menores prohibidos aumenta para valores mayores de k . Para los 3-árboles parciales hay cuatro menores prohibidos: el grafo completo de cinco vértices, el grafo octaédrico de seis vértices, el grafo de Wagner de ocho vértices y el prisma pentagonal de diez vértices. ^{[ 2 ]}

Muchos problemas algorítmicos que son NP-completos para grafos arbitrarios pueden resolverse eficientemente para k -árboles parciales mediante programación dinámica , utilizando las descomposiciones en árbol de estos grafos. ^{[ 3 ]}

Si una familia de grafos tiene un ancho de árbol acotado , entonces es una subfamilia de los k- árboles parciales, donde k es el límite del ancho de árbol. Las familias de grafos con esta propiedad incluyen los grafos cactus , los pseudobosques , los grafos serie-paralelo , los grafos planares externos , los grafos de Halin y las redes apolíneas . ^{[ 2 ]} Por ejemplo, los grafos serie-paralelo son una subfamilia de los 2-árboles parciales, y más fuertemente un grafo es un 2-árbol parcial si y solo si cada uno de sus componentes biconexos es serie-paralelo.

Los grafos de flujo de control que surgen en la compilación de programas estructurados también tienen un ancho de árbol limitado, lo que permite realizar ciertas tareas, como la asignación de registros, de manera eficiente en ellos. ^{[ 4 ]}