Descomposición de los árboles

Representación gráfica de un árbol

Un gráfico con ocho vértices y una descomposición en árbol del mismo en un árbol con seis nodos. Cada arista del gráfico conecta dos vértices que se enumeran juntos en algún nodo del árbol, y cada vértice del gráfico se enumera en los nodos de un subárbol contiguo del árbol. Cada nodo del árbol enumera como máximo tres vértices, por lo que el ancho de esta descomposición es dos.

En teoría de grafos , una descomposición en árbol es un mapeo de un gráfico en un árbol que puede usarse para definir el ancho del árbol del gráfico y acelerar la resolución de ciertos problemas computacionales en el gráfico.

Las descomposiciones de árboles también se denominan árboles de unión , árboles de clique o árboles de unión . Desempeñan un papel importante en problemas como la inferencia probabilística , la satisfacción de restricciones , la optimización de consultas ^[1] y la descomposición matricial .

El concepto de descomposición arbórea fue introducido originalmente por Rudolf Halin  (1976). Más tarde fue redescubierto por Neil Robertson y Paul Seymour  (1984) y desde entonces ha sido estudiado por muchos otros autores. ^[2]

Definición

Intuitivamente, una descomposición en árbol representa los vértices de un grafo G dado como subárboles de un árbol, de tal manera que los vértices en G son adyacentes solo cuando los subárboles correspondientes se intersecan. Por lo tanto, G forma un subgrafo del grafo de intersección de los subárboles. El grafo de intersección completo es un grafo cordal .

Cada subárbol asocia un vértice del grafo a un conjunto de nodos del árbol. Para definir esto formalmente, representamos cada nodo del árbol como el conjunto de vértices asociados a él. Así, dado un grafo G = ( V , E ) , una descomposición en árbol es un par ( X , T ) , donde X = { X ₁ , …, X _n } es una familia de subconjuntos (a veces llamados bolsas ) de V , y T es un árbol cuyos nodos son los subconjuntos X _i , que satisfacen las siguientes propiedades: ^[3]

1. La unión de todos los conjuntos Xi _es igual a V. Es decir, cada vértice del grafo está asociado con al menos un nodo del árbol.
2. Para cada arista ( v , w ) del grafo, existe un subconjunto Xi que contiene tanto a v como _a w . Es decir, los vértices son adyacentes en el grafo solo cuando los subárboles correspondientes tienen un nodo en común.
3. Si X _i y X _j contienen ambos un vértice v , entonces todos los nodos X _k del árbol en la ruta (única) entre X _i y X _j contienen también v . Es decir, los nodos asociados con el vértice v forman un subconjunto conectado de T . Esto también se conoce como coherencia o propiedad de intersección continua . Se puede afirmar de forma equivalente que si X _i , X _j y X _k son nodos, y X _k está en la ruta de X _i a X _j , entonces . ${\displaystyle X_{i}\cap X_{j}\subseteq X_{k}}$

La descomposición en árbol de un gráfico está lejos de ser única; por ejemplo, una descomposición en árbol trivial contiene todos los vértices del gráfico en su único nodo raíz.

Una descomposición de árbol en la que el árbol subyacente es un gráfico de ruta se denomina descomposición de ruta, y el parámetro de ancho derivado de estos tipos especiales de descomposiciones de árbol se conoce como pathwidth .

Una descomposición de árbol ( X , T = ( I , F )) de ancho de árbol k es suave , si para todos , y para todos . ^[4] ${\displaystyle i\in I:|X_{i}|=k+1}$ ${\displaystyle (i,j)\in F:|X_{i}\cap X_{j}|=k}$

Ancho del árbol

Dos descomposiciones de árbol diferentes del mismo gráfico

El ancho de una descomposición en árbol es el tamaño de su conjunto más grande X _i menos uno. El ancho de árbol tw( G ) de un grafo G es el ancho mínimo entre todas las descomposiciones en árbol posibles de G . En esta definición, el tamaño del conjunto más grande se reduce en uno para que el ancho de árbol de un árbol sea igual a uno. El ancho de árbol también se puede definir a partir de otras estructuras distintas de las descomposiciones en árbol, incluidos los grafos cordales , zarzas y havens .

Es NP-completo determinar si un gráfico dado G tiene un ancho de árbol como máximo de una variable dada k . ^[5] Sin embargo, cuando k es cualquier constante fija, los gráficos con ancho de árbol k se pueden reconocer y se puede construir una descomposición de árbol de ancho k para ellos, en tiempo lineal. ^[4] La dependencia temporal de este algoritmo en k es una función exponencial de k ³ .

Programación dinámica

A principios de la década de 1970, se observó que una gran clase de problemas de optimización combinatoria definidos en grafos se podían resolver de manera eficiente mediante programación dinámica no serial siempre que el grafo tuviera una dimensión acotada , ^[6] un parámetro relacionado con el ancho del árbol. Más tarde, varios autores observaron de manera independiente, a fines de la década de 1980, ^[7] que muchos problemas algorítmicos que son NP-completos para grafos arbitrarios se pueden resolver de manera eficiente mediante programación dinámica para grafos de ancho de árbol acotado, utilizando las descomposiciones en árbol de estos grafos.

Como ejemplo, considere el problema de encontrar el conjunto independiente máximo en un grafo de ancho de árbol k . Para resolver este problema, primero elija uno de los nodos de la descomposición del árbol como raíz, arbitrariamente. Para un nodo X _i de la descomposición del árbol, sea D _i la unión de los conjuntos X _j que descienden de X _i . Para un conjunto independiente, sea A ( S , i ) el tamaño del subconjunto independiente más grande I de D _i tal que De manera similar, para un par adyacente de nodos X _i y X _j , con X _i más alejado de la raíz del árbol que X _j , y un conjunto independiente, sea B ( S , i , j ) el tamaño del subconjunto independiente más grande I de D _i tal que Podemos calcular estos valores de A y B mediante un recorrido de abajo hacia arriba del árbol: ${\displaystyle S\subset X_{i},}$ ${\displaystyle I\cap X_{i}=S.}$ ${\displaystyle S\subset X_{i}\cap X_{j},}$ ${\displaystyle I\cap X_{i}\cap X_{j}=S.}$

${\displaystyle A(S,i)=|S|+\sum _{j}\left(B(S\cap X_{j},j,i)-|S\cap X_{j}|\right)}$

${\displaystyle B(S,i,j)=\max _{S'\subset X_{i} \atop S=S'\cap X_{j}}A(S',i)}$

donde la suma en el cálculo de es sobre los hijos del nodo X _i . ${\displaystyle A(S,i)}$

En cada nodo o borde, hay como máximo 2 ^k conjuntos S para los que necesitamos calcular estos valores, por lo que si k es una constante, entonces todo el cálculo toma un tiempo constante por borde o nodo. El tamaño del conjunto independiente máximo es el valor más grande almacenado en el nodo raíz, y el conjunto independiente máximo en sí se puede encontrar (como es estándar en algoritmos de programación dinámica) retrocediendo a través de estos valores almacenados comenzando desde este valor más grande. Por lo tanto, en grafos de ancho de árbol acotado, el problema del conjunto independiente máximo se puede resolver en tiempo lineal. Algoritmos similares se aplican a muchos otros problemas de grafos.

Este enfoque de programación dinámica se utiliza en el aprendizaje automático a través del algoritmo de árbol de unión para la propagación de creencias en gráficos de ancho de árbol acotado. También desempeña un papel clave en los algoritmos para calcular el ancho de árbol y construir descomposiciones de árboles: normalmente, dichos algoritmos tienen un primer paso que aproxima el ancho de árbol, construyendo una descomposición de árbol con este ancho aproximado, y luego un segundo paso que realiza una programación dinámica en la descomposición de árbol aproximada para calcular el valor exacto del ancho de árbol. ^[4]

Véase también

• Zarzas y refugios  : dos tipos de estructuras que pueden utilizarse como alternativa a la descomposición en árboles para definir el ancho de árbol de un gráfico.
• Descomposición de ramas  : Una estructura estrechamente relacionada cuyo ancho está dentro de un factor constante del ancho del árbol.
• Método de descomposición  : la descomposición en árbol se utiliza en el método de descomposición para resolver problemas de satisfacción de restricciones.

Notas

1. Gottlob y otros (2012).
2. Diestel (2005) págs. 354-355
3. Diestel (2005) sección 12.3
4. Bodlaender (1996).
5. Arnborg, Corneil y Proskurowski (1987).
6. Bertelé y Brioschi (1972).
7. Arnborg y Proskurowski (1989); Berna, Lawler y Wong (1987); Bodlaender (1988).

Referencias

• Arnborg, S.; Corneil, D .; Proskurowski, A. (1987), "Complejidad de la búsqueda de incrustaciones en un árbol k ", SIAM Journal on Matrix Analysis and Applications , 8 (2): 277–284, doi :10.1137/0608024.
• Arnborg, S.; Proskurowski, A. (1989), "Algoritmos de tiempo lineal para problemas NP-hard restringidos a árboles k parciales ", Discrete Applied Mathematics , 23 (1): 11–24, doi : 10.1016/0166-218X(89)90031-0.
• Bern, MW; Lawler, EL ; Wong, AL (1987), "Cálculo en tiempo lineal de subgrafos óptimos de grafos descomponibles", Journal of Algorithms , 8 (2): 216–235, doi :10.1016/0196-6774(87)90039-3.
• Bertelé, Umberto; Brioschi, Francesco (1972), Programación dinámica no serial , Academic Press, ISBN 0-12-093450-7.
• Bodlaender, Hans L. (1988), "Programación dinámica en grafos con ancho de árbol limitado", Proc. 15th International Colloquium on Automata, Languages ​​and Programming , Notas de clase en informática, vol. 317, Springer-Verlag, págs. 105–118, doi :10.1007/3-540-19488-6_110, hdl : 1874/16258 , ISBN 978-3-540-19488-0.
• Bodlaender, Hans L. (1996), "Un algoritmo de tiempo lineal para encontrar descomposiciones de árboles de ancho de árbol pequeño", SIAM Journal on Computing , 25 (6): 1305–1317, CiteSeerX  10.1.1.113.4539 , doi :10.1137/S0097539793251219.
• Diestel, Reinhard (2005), Teoría de grafos (3.ª ed.), Springer , ISBN 3-540-26182-6.
• Gottlob, Georg; Lee, Stephanie Tien; Valiant, Gregory; Valiant, Paul (2012), "Límites de tamaño y ancho de árbol para consultas conjuntivas", Journal of the ACM , 59 (3): A16:1–A16:35, doi :10.1145/2220357.2220363, MR  2946220
• Halin, Rudolf (1976), " Funciones S para gráficos", Journal of Geometry , 8 (1–2): 171–186, doi :10.1007/BF01917434, S2CID  120256194.
• Robertson, Neil ; Seymour, Paul D. (1984), "Graph minors III: Planar tree-width", Journal of Combinatorial Theory , Serie B, 36 (1): 49–64, doi : 10.1016/0095-8956(84)90013-3.