Ancho del árbol

Para cualquier constante fija${\displaystyle k}$, los gráficos de ancho de árbol como máximo${\displaystyle k}$se denominan parciales${\displaystyle k}$-árboles. Otras familias de grafos con ancho de árbol limitado incluyen los grafos cactus , los pseudobosques , los grafos serie-paralelo , los grafos exteriores planares , los grafos de Halin y las redes apolíneas . ^{[ 5 ]} 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. ^{[ 6 ]}

Los grafos planares no tienen ancho de árbol limitado, porque${\displaystyle n\times n}$El grafo de cuadrícula es un grafo planar con un ancho de árbol exactamente${\displaystyle n}$. Por lo tanto, si${\displaystyle F}$es una familia de grafos cerrada por menor con ancho de árbol limitado, no puede incluir todos los grafos planares. Por el contrario, si algún grafo planar no puede aparecer como menor para los grafos en la familia${\displaystyle F}$, entonces hay una constante${\displaystyle k}$de tal manera que todos los gráficos en${\displaystyle F}$tener ancho de árbol como máximo${\displaystyle k}$. Es decir, las siguientes tres condiciones son equivalentes entre sí: ^{[ 7 ]}

1. ${\displaystyle F}$es una familia cerrada menor de grafos de ancho de árbol acotado;
2. Uno de los pocos menores prohibidos que caracterizan${\displaystyle F}$es planar;
3. ${\displaystyle F}$es una familia de grafos cerrados menores que no incluye todos los grafos planares.

Para cada valor finito de${\displaystyle k}$, los gráficos de ancho de árbol como máximo${\displaystyle k}$puede caracterizarse por un conjunto finito de menores prohibidos . (Es decir, cualquier grafo de ancho de árbol mayor que${\displaystyle k}$incluye uno de los grafos del conjunto como menor.) Cada uno de estos conjuntos de menores prohibidos incluye al menos un grafo planar.

• Para${\displaystyle k=1}$, el único menor prohibido es un grafo de ciclo de 3 vértices . ^{[ 5 ]}
• Para${\displaystyle k=2}$, el único menor prohibido es el grafo completo de 4 vértices${\displaystyle K_{4}}$. ^{[ 5 ]}
• Para${\displaystyle k=3}$Hay cuatro menores prohibidos:${\displaystyle K_{5}}$, el gráfico del octaedro , el gráfico del prisma pentagonal y el gráfico de Wagner . De estos, los dos gráficos poliédricos son planares. ^{[ 8 ]}

Para valores mayores de${\displaystyle k}$, el número de menores prohibidos crece al menos tan rápido como una función exponencial de${\displaystyle {\sqrt {k}}}$. ^{[ 9 ]} Sin embargo, los límites superiores conocidos sobre el tamaño y el número de menores prohibidos son mucho mayores que este límite inferior. ^{[ 10 ]}

Es${\displaystyle {\mathsf {NP}}}$-completar para determinar si un gráfico dado${\displaystyle G}$tiene un ancho de árbol como máximo una variable dada${\displaystyle k}$. ^{[ 11 ]} Sin embargo, cuando${\displaystyle k}$es cualquier constante fija, los gráficos con ancho de árbol${\displaystyle k}$se puede reconocer y un ancho${\displaystyle k}$descomposición de árbol construida para ellos, en tiempo lineal. ^{[ 12 ]} La dependencia temporal de este algoritmo en${\displaystyle k}$es exponencial.

Debido a la importancia del ancho de árbol en una gran cantidad de campos, se han desarrollado diferentes algoritmos prácticos y teóricos para calcularlo. Dependiendo de la aplicación, se puede preferir una mejor relación de aproximación o una mejor dependencia del tiempo de ejecución con respecto al tamaño de la entrada o al ancho de árbol. La siguiente tabla ofrece una visión general de algunos algoritmos para calcular el ancho de árbol.${\displaystyle k}$es el ancho del árbol y${\displaystyle n}$es el número de vértices de un grafo de entrada${\displaystyle G}$Cada uno de los algoritmos produce una salida en el tiempo${\displaystyle f(k)\cdot g(n)}$una descomposición del ancho dada en la columna Aproximación. Por ejemplo, el algoritmo de Bodlaender (1996) en tiempo${\displaystyle 2^{O(k^{3})}\cdot n}$o bien construye una descomposición en árbol del grafo de entrada.${\displaystyle G}$de ancho como máximo${\displaystyle k}$o informa que el ancho del árbol de${\displaystyle G}$es más que${\displaystyle k}$. De manera similar, el algoritmo de Bodlaender et al. (2016) en tiempo${\displaystyle 2^{O(k)}\cdot n}$o bien construye una descomposición en árbol del grafo de entrada.${\displaystyle G}$de ancho como máximo${\displaystyle 5k+4}$o informa que el ancho del árbol de${\displaystyle G}$es más que${\displaystyle k}$. Korhonen (2021) mejoró el ancho de la descomposición a${\displaystyle 2k+1}$en el mismo tiempo de ejecución.

No se sabe si determinar el ancho de árbol de los grafos planares es NP-completo, o si su ancho de árbol se puede calcular en tiempo polinomial . ^{[ 13 ]}

En la práctica, un algoritmo de Shoikhet y Geiger (1997) puede determinar el ancho de árbol de grafos con hasta 100 vértices y ancho de árbol de hasta 11, encontrando una completación cordal de estos grafos con el ancho de árbol óptimo.

Para grafos más grandes, se pueden usar técnicas basadas en búsqueda, como la búsqueda de ramificación y acotación, para calcular el ancho del árbol. Estos algoritmos son de ejecución en cualquier momento , ya que si se detienen prematuramente, arrojarán una cota superior para el ancho del árbol. Un algoritmo de este tipo fue propuesto en 2004 por Vibhav Gogate y Rina Dechter . Para proporcionar una cota inferior para el ancho del árbol en las ramas de esta búsqueda, construyen un menor del grafo contrayendo repetidamente una arista entre un vértice de grado mínimo y uno de sus vecinos, hasta que solo queda un vértice. El máximo del grado mínimo sobre estos menores construidos garantiza una cota inferior para el ancho del árbol del grafo. ^{[ 14 ]} Alex Dow y Rich Korf mejoraron aún más este algoritmo usando la búsqueda primero en amplitud . ^{[ 15 ]}

A principios de la década de 1970, se observó que una gran clase de problemas de optimización combinatoria definidos en grafos podían resolverse eficientemente mediante programación dinámica no serial siempre que el grafo tuviera una dimensión acotada , ^{[ 16 ]} un parámetro que Bodlaender (1998) demostró que era equivalente al ancho del árbol . Posteriormente, varios autores observaron independientemente a finales de la década de 1980 ^{[ 17 ]} que muchos problemas algorítmicos que son NP-completos para grafos arbitrarios pueden resolverse eficientemente mediante programación dinámica para grafos de ancho de árbol acotado, utilizando las descomposiciones en árbol de estos grafos.

Como ejemplo, el problema de colorear un grafo de ancho de árbol.${\displaystyle k}$puede resolverse utilizando un algoritmo de programación dinámica en una descomposición en árbol del grafo. Para cada bolsa${\displaystyle X_{i}}$de la descomposición del árbol y cada partición de los vértices de${\displaystyle X_{i}}$en clases de color, el algoritmo determina si ese coloreado es válido y puede extenderse a todos los nodos descendientes en la descomposición del árbol, combinando información de un tipo similar calculada y almacenada en esos nodos. El algoritmo resultante encuentra un coloreado óptimo de un${\displaystyle n}$-grafo de vértices en el tiempo${\displaystyle O(k^{k+O(1)}n)}$, un límite de tiempo que hace que este problema sea tratable con parámetros fijos .

Para una amplia clase de problemas, existe un algoritmo de tiempo lineal para resolver un problema de dicha clase si se proporciona una descomposición en árbol con ancho de árbol constante y acotado. Específicamente, el teorema de Courcelle ^{[ 18 ]} establece que si un problema de grafos puede expresarse en la lógica de grafos utilizando lógica monádica de segundo orden , entonces puede resolverse en tiempo lineal en grafos con ancho de árbol acotado. La lógica monádica de segundo orden es un lenguaje para describir propiedades de grafos que utiliza las siguientes construcciones:

• Operaciones lógicas, como${\displaystyle \wedge ,\vee ,\neg ,\Rightarrow }$
• Pruebas de pertenencia, como${\displaystyle e\in E}$,${\displaystyle v\in V}$
• Cuantificaciones sobre vértices, aristas, conjuntos de vértices y/o conjuntos de aristas, tales como:${\displaystyle \forall v\in V}$,${\displaystyle \exists e\in E}$,${\displaystyle \exists I\subset V}$,${\displaystyle \forall F\subset E}$
• Pruebas de incidencia vértice-arista (${\displaystyle u}$es un punto final de${\displaystyle e}$), y algunas extensiones que permiten cosas como la optimización.

Consideremos, por ejemplo, el problema de 3-coloración para grafos. Para un grafo${\displaystyle G=(V,E)}$, este problema pregunta si es posible asignar a cada vértice${\displaystyle v\in V}$uno de tres colores de tal manera que no se asignen dos vértices adyacentes del mismo color. Este problema se puede expresar en lógica monádica de segundo orden como $${\displaystyle \exists W_{1}\subseteq V\ \exists W_{2}\subseteq V\ \exists W_{3}\subseteq V\ \left({\begin{aligned}&\forall v\in V\ (v\in W_{1}\vee v\in W_{2}\vee v\in W_{3})\wedge {}\\&\operatorname {independent} (W_{1})\wedge {}\\&\operatorname {independent} (W_{2})\wedge {}\\&\operatorname {independent} (W_{3})\\\end{aligned}}\right),}$$ dónde${\displaystyle W_{1}}$,${\displaystyle W_{2}}$,${\displaystyle W_{3}}$representan los subconjuntos de vértices que tienen cada uno de los tres colores, y donde las subexpresiones${\displaystyle \operatorname {independent} (W_{i})}$se definen para significar $${\displaystyle \operatorname {independent} (W_{i})\equiv \forall e\in E\ \exists v\in V\ (\operatorname {endpoint} (v,e)\wedge \neg v\in W_{i}).}$$ (No es necesario incluir en esta fórmula el requisito de que los conjuntos${\displaystyle W_{i}}$ser disjuntos.) Por lo tanto, según los resultados de Courcelle, el problema de 3-coloración se puede resolver en tiempo lineal para un grafo dado una descomposición en árbol de ancho de árbol constante acotado.

El ancho de camino de un grafo tiene una definición muy similar al ancho de árbol mediante descomposiciones de árbol, pero está restringido a descomposiciones de árbol en las que el árbol subyacente de la descomposición es un grafo de camino . Alternativamente, el ancho de camino puede definirse a partir de grafos de intervalo de forma análoga a la definición de ancho de árbol a partir de grafos cordales. Como consecuencia, el ancho de camino de un grafo es siempre al menos tan grande como su ancho de árbol, pero solo puede ser mayor por un factor logarítmico. ^{[ 5 ]} Otro parámetro, el ancho de banda del grafo , tiene una definición análoga a partir de grafos de intervalo propios , y es al menos tan grande como el ancho de camino. Otros parámetros relacionados incluyen la profundidad del árbol , un número que está acotado para una familia de grafos cerrados en menores si y solo si la familia excluye un camino, y la degeneración , una medida de la dispersión de un grafo que es como máximo igual a su ancho de árbol.

Debido al ancho del árbol de un${\displaystyle n\times n}$El gráfico de cuadrícula es${\displaystyle n}$, el ancho de árbol de un grafo${\displaystyle G}$siempre es mayor o igual que el tamaño de la cuadrícula cuadrada más grande menor de${\displaystyle G}$. En la otra dirección, el teorema del menor de la cuadrícula de Robertson y Seymour muestra que existe una función no acotada${\displaystyle f}$de tal manera que el cuadrado más grande de la cuadrícula menor de un grafo de ancho de árbol${\displaystyle k}$tiene tamaño al menos${\displaystyle f(k)}$. ^{[ 19 ]} Los mejores límites conocidos en${\displaystyle f}$son que${\displaystyle f}$debe ser al menos${\displaystyle \Omega (k^{d})}$para alguna constante fija${\displaystyle d>0}$y como máximo ^{[ 20 ]}$${\displaystyle O\left({\sqrt {r/\log r}}\right).}$$

(Para el${\displaystyle \Omega }$notación en el límite inferior, véase la notación O grande .) Se conocen límites más ajustados para familias de grafos restringidas, lo que conduce a algoritmos eficientes para muchos problemas de optimización de grafos en esas familias a través de la teoría de la bidimensionalidad . ^{[ 21 ]} El teorema de la cuadrícula de Halin proporciona un análogo de la relación entre el ancho del árbol y el tamaño del menor de la cuadrícula para grafos infinitos. ^{[ 22 ]}

Una familia${\displaystyle F}$Se dice que una familia de grafos cerrados bajo la operación de tomar subgrafos tiene un ancho de árbol local acotado , o la propiedad diámetro-ancho de árbol , si el ancho de árbol de los grafos de la familia está acotado superiormente por una función de su diámetro . Si además se supone que la clase es cerrada bajo la operación de tomar menores , entonces${\displaystyle F}$tiene ancho de árbol local limitado si y solo si uno de los menores prohibidos para${\displaystyle F}$es un grafo ápice . ^{[ 23 ]} Las demostraciones originales de este resultado mostraron que el ancho de árbol en una familia de grafos sin ápice-menor crece como máximo doblemente exponencialmente en función del diámetro; ^{[ 24 ]} posteriormente esto se redujo a exponencial simple ^{[ 21 ]} y finalmente a una cota lineal. ^{[ 25 ]} El ancho de árbol local acotado está estrechamente relacionado con la teoría algorítmica de la bidimensionalidad , ^{[ 26 ]} y cada propiedad de grafo definible en lógica de primer orden puede decidirse para una familia de grafos sin ápice-menor en una cantidad de tiempo que es solo ligeramente superlineal. ^{[ 27 ]}

También es posible que una clase de grafos que no es cerrada bajo menores tenga un ancho de árbol local acotado. En particular, esto es trivialmente cierto para una clase de grafos de grado acotado, ya que los subgrafos de diámetro acotado tienen un tamaño acotado. Otro ejemplo lo proporcionan los grafos 1-planares , grafos que se pueden dibujar en el plano con un cruce por arista, y más generalmente para los grafos que se pueden dibujar en una superficie de género acotado con un número acotado de cruces por arista. Al igual que con las familias de grafos cerrados bajo menores con ancho de árbol local acotado, esta propiedad ha allanado el camino hacia algoritmos de aproximación eficientes para estos grafos. ^{[ 28 ]}

Halin (1976) define una clase de parámetros de grafos que él llama funciones S , que incluyen el ancho del árbol. Se requiere que estas funciones de grafos a enteros sean cero en grafos sin aristas , para ser monótonas menores (una función${\displaystyle f}$se denomina "monótono menor" si, siempre que${\displaystyle H}$es menor de edad${\displaystyle G}$, uno tiene${\displaystyle f(H)\leq f(G)}$), para incrementarse en uno cuando se agrega un nuevo vértice que es adyacente a todos los vértices anteriores , y para tomar el valor mayor de los dos subgrafos a cada lado de un separador de clique . El conjunto de todas estas funciones forma un retículo completo bajo las operaciones de minimización y maximización elemento a elemento. El elemento superior de este retículo es el ancho del árbol, y el elemento inferior es el número de Hadwiger , el tamaño del menor completo más grande en el grafo dado.