Encontrar la trisección más par de un grafo en tiempo O(n)

Question

He estado trabajando en esto durante unos días, repasando la teoría de los grafos y los conjuntos disjuntos, pero todavía no he encontrado un algoritmo que garantice el resultado óptimo y que se ejecute en mejor que $O(n^2)$ tiempo.

Planteamiento del problema

El problema es dividir un gráfico de árbol que es un grafo no dirigido conectado y sin ciclos, en 3 partes iguales. Más formalmente, dado un gráfico de árbol $G$ con $n$ vértices, encontrar la partición más uniforme de $G$ en $3$ componentes $A, B, C$ con $a, b, c$ vértices, respectivamente. Para este problema, "más par" se define como tener el mayor valor de $abc$ posible para el gráfico dado $G$ .

Lo que más me interesa saber es si hay propiedades de los grafos arbóreos que pueda aprovechar para demostrar que una trisección es la mejor (la más uniforme) posible sin tener que probar (en casos patológicos) todas las trisecciones posibles. Por ejemplo, si la bisección más pareja es tan desigual que la "mitad" más pequeña tiene $s$ vértices tales que $s < n/3$ , lo que significa que el vértice de la mitad mayor al que se le acaba de cortar la arista sólo tiene cortes restantes de tamaño $r \le s$ . Así que ahora sabemos $s < n/3$ , $r < n/3$ y ninguno de los dos puede ser más grande en un corte de 3.

Discusión

Nota : Esta sección de discusión es en la que muestro los avances que había hecho en la reflexión sobre la realización de lo que es la trisección óptima de un árbol en el momento en que publiqué la pregunta. Lo dejo aquí para que quede constancia, pero en su mayor parte no es tan útil excepto para mostrar por qué la respuesta no es obvia si no se sabe que todo árbol tiene un centro.

Creo que es correcto extender este razonamiento para decir que para la trisección de $G$ en $A$ , $B$ y $C$ , donde $B$ es el componente que se encuentra en el centro (es decir, que podría estar conectado a cualquiera de los dos $A$ o $C$ restaurando una sola arista de corte), la trisección es óptima si $(A, B)$ es la bisección óptima de $G - C$ y $(B, C)$ es la bisección óptima de $G - A$ . Desgraciadamente, aún no he reflexionado lo suficiente como para estar seguro de que la trisección óptima es la única $(A, B, C)$ para los que se cumple esa condición.

Para la trisección óptima de $G$ en $(A, B, C)$ con tallas $a$ , $b$ y $c$ podemos etiquetarlas arbitrariamente según su tamaño, de forma que $a \ge b \ge c$ . Entonces sabemos que $c\le n/3$ y $c \le {(b + c)}/2$ .

También sabemos que la trisección óptima tiene $c$ lo más grande posible. Del mismo modo, sabemos que la bisección óptima de $B+C$ o $A+C$ tiene la mayor $c$ posible, aunque no hay garantía de que ambos $B+C$ y $A+C$ están completamente conectados en primer lugar.

Póngalos juntos y demuestran que dado cualquier corte de $G$ a los componentes $X$ y $Y$ la mejor trisección de G dado ese corte es $X$ más la mejor bisección de $Y$ o es $Y$ más la mejor bisección de $X$ . A partir de ahora llamaré a los vértices "nodos" porque es una palabra más corta.

Es fácil cortar el gráfico óptimamente por la mitad en $O(n)$ tiempo. Cada arista tiene $x$ nodos en un lado y $(n-x)$ por el otro. Como sólo hay un camino desde cualquier nodo a cualquier otro, se pueden calcular estos valores para cada arista en $O(n)$ tiempo, y mientras lo calculas, puedes llevar la cuenta de cuál es el borde más cercano a $n \over 2$ nodos en un lado de la misma. Como ha comprobado cada arista, sabe que esto es lo mejor que puede hacer, incluso si $x \ll \frac n2$ . Puede que no sea la única arista que produzca particiones de ese tamaño, pero eso no es motivo de preocupación.

Sin embargo, hasta ahora no he encontrado una forma de demostrar que un par de aristas dado es la mejor opción para cortar para particionar no triviales $G$ a menos que (a) el resultado sea perfecto, o (b) lo compare con cualquier otra combinación de 2 aristas. En realidad, no tengo que comparar cada combinación todo el tiempo, a menudo puedo reducir el espacio de búsqueda, pero no he descubierto cómo demostrar que he encontrado la mejor partición posible en menos que $O(n^2)$ tiempo.

Puedo precomputar mucho, pero cuando elijo un candidato para la primera de las 2 aristas para trisecar el árbol, no he encontrado nada que pueda precomputar en $O(n \log n)$ tiempo que resulta en un $O(1)$ manera de saber cuál de las aristas restantes está en cuál de los 2 componentes resultantes y mantener las aristas de un componente fuera de la búsqueda binaria de la mejor arista coincidente en el otro componente.

Todo lo que se me ha ocurrido hasta ahora falla para varios tipos de casos límite. El caso más simple es un árbol de estrellas, $n$ nodos conectados a un nodo central de grado $n$ . Si lo único que hago es comparar ingenuamente los bordes y los cortes, tengo que probar todas las combinaciones posibles.

Puedo clasificar las aristas, como hice con la bisección del gráfico, excepto que esta vez las clasifico según lo cerca que estén de tener $n \over 3$ nodos en un lado, pero lo que si tengo un árbol como este:

$H$ está conectado a 5 hojas y hay un total de 12 nodos en $G$ . El borde más cercano a tener $\frac n3 = 4$ nodos en un lado es el borde entre $4$ y $5$ , $(4,5)$ , que divide $G$ en conjuntos de 4 y 8 nodos. Si corto esa arista, las siguientes mejores aristas a cortar (si sólo estoy mirando aristas de $G$ y siguiendo la clasificación del párrafo anterior) son $(3,4)$ o $(5,6)$ pero que daría lugar a particiones de $\{8,1,3\}$ y $\{7,1,4\}$ respectivamente. Pasará mucho tiempo hasta que encuentre la solución óptima de $\{6,3,3\}$ .

Mirando esto, consideré encontrar la mejor $\frac 23$ cortar y luego cortar el conjunto más grande por la mitad. A excepción de este gráfico, el mejor $\frac 23$ corte es el mismo que el mejor $\frac 13$ corte, por lo que cortaríamos los bordes $(4,5)$ y $(H,6)$ dándonos una $\{6,2,4\}$ partición.

Como bisecar el gráfico es fácil, he mirado de bisecar recursivamente el gráfico. Podría construir un árbol binario equilibrado de subgrafos, pero no sé lo que conseguiría para un gráfico de estrellas o varios tipos de gráficos asimétricos que se me ocurran. Podría funcionar para encontrar una respuesta aproximada, pero quiero estar seguro de tener la mejor respuesta exacta.

Los gráficos reales que estoy tratando pueden ser enormes, hasta $1,000,000$ vértices, por lo que el $O(n^2)$ solución no es práctica. La única restricción real en la que puedo confiar es que el diámetro del gráfico no se descontrole de forma enorme.

Busco ayuda para encontrar las mejores aristas para cortar o ayuda para verificar que la partición que he encontrado es la mejor posible para el gráfico dado (o, por supuesto, ambas cosas).

Answer 1

La solución

La pieza que faltaba en el rompecabezas

La propiedad de los grafos arbóreos que no conocía ni intuía y que necesitaba conocer para poder encontrar el $O(n \log n)$ es que para cada árbol de $n$ puede elegir una raíz tal que ningún subárbol tenga más de $n/2$ nodos, o, como dijo @Dap, cada gráfico de árbol $G$ tiene al menos $1$ vértice $r$ de manera que los componentes de $G-r$ todos tienen un orden como máximo $n/2$ o todo árbol tiene un centro . Una vez que sabes eso, todo lo demás encaja.

Introducción

Las respuestas de Dap y SmileyCraft contenían elementos útiles, pero eran demasiado complicadas y no pude demostrar que su complejidad en el peor de los casos fuera mejor que $O(n^2)$ aunque probablemente sean mejores que eso. Mi solución es bastante parecida a la de Dap, pero más sencilla. Para mí, sin embargo, era la simplificación que me interesaba más que la solución real.

Como los grafos arbóreos son tan especiales, se habla de ellos en la teoría de grafos, en la teoría de conjuntos y en la informática, a veces con nombres y símbolos diferentes, como habrás notado si has leído las otras respuestas a esta pregunta. También tienen un montón de propiedades y operaciones con nombres especiales. Tanto es así que he hecho un Glosario y lo he incluido al final de esta respuesta. Por favor, consúltalo si te sientes confundido por alguno de los términos que utilizo o por la forma en que los uso.

Cuando hablo de un árbol (en lugar de un gráfico de árbol), me refiero a un árbol jerárquico como el que se utiliza habitualmente en informática, con una raíz, ramas, hijos, etc. Cuando me refiero a "un corte en el subárbol $b$ " de un árbol, me refiero a cortar $b$ de la raíz (y por tanto del resto) del árbol o cortar una arista perteneciente al subárbol $b$ . En la teoría de grafos, el peso de un corte es el número de aristas cortadas, pero con los árboles, ese número es siempre 1, por lo que el peso de un corte no es tan interesante, y a veces uso "peso del corte" como abreviatura para referirme al tamaño del subárbol creado por el corte.

Siempre que hablo de peso o pesadez, me refiero al número de nodos de algún subárbol o al número de nodos que quedan en el otro árbol tras eliminar uno o varios subárboles. Esto se corresponde con el orden de la componente del gráfico del árbol representada por esos nodos del árbol.

No voy a intentar demostrarlo todo. Empecé a hacerlo pero se me hizo largo y tedioso. Déjame un comentario si crees que he afirmado algo que no es cierto y quizá añada una prueba más adelante.

• El objetivo es encontrar la trisección óptima de un Árbol Gráfico en $O(n \log n)$ tiempo.
• "Óptimo" se define como $\max(abc)$ , donde $a$ , $b$ y $c$ son los tamaños de los tres componentes que quedan después de la trisección.

Parte 1: Convertir el gráfico de árbol en el tipo de árbol adecuado

• Encontrar el vértice $r$ de manera que los componentes de $G-r$ todos tienen un orden como máximo $n/2$ . Está garantizado que habrá al menos $1$ dicho vértice.
• Convertir en un árbol jerárquico enraizando el gráfico de árbol en $r$ .

El árbol resultante tiene unas propiedades estupendas. En particular, tiene un subárbol que llamaré el "subárbol pesado" que contiene tantos o más nodos que cualquier otro subárbol, pero al mismo tiempo se garantiza que tiene peso $h \le n/2$ .

Parte 2: Operar en el árbol

Encontrar la mejor bisección en $O(n)$

Podemos crear el árbol descrito anteriormente, incluyendo el cálculo del peso de cada nodo y la búsqueda del subárbol pesado, en $O(n)$ .

La bisección óptima del Árbol Gráfico se obtiene cortando la arista entre la raíz del árbol y el subárbol pesado.

Demuestre que esto es cierto

Ten en cuenta que para los enteros, $x > y \iff (x-1)(y+1) > xy$ .

Por definición, el peso del subárbol pesado $h \le n/2$ y, por tanto, el número de nodos que no están en él son $r = n - h$ . También, $h \ge$ el peso de cualquier otro subárbol $s$ . Dado que cualquier subárbol de un árbol es más pequeño que el árbol completo, $h > s \iff h >$ el peso de cualquier subárbol de $s$ . Así que $r \ge h \ge s \ge$ cualquier otro subárbol. Así que $rh$ es el producto del $2$ números más grandes y cercanos que podemos hacer y, por lo tanto, es lo mejor que podemos hacer.

Encontrar la mejor trisección en $O(n \log n)$

La otra pieza que faltaba

La mejor trisección requiere al menos $1$ (En realidad, debido a la simetría, esto es un poco exagerado. Formalmente, al menos $1$ elemento del conjunto de trisecciones equivalentemente óptimas puede hacerse mediante un corte en el subárbol pesado).

El mismo razonamiento que prueba el corte del subárbol pesado $h$ hace la mejor bisección demuestra que cualquier trisección hecha con 2 cortes no en $h$ no empeoraría por el recorte $h$ en lugar de cualquiera de los otros 2 cortes.

Dejemos que $h$ sea el peso del subárbol pesado, $x$ y $y$ sea el peso de los 2 subárboles cortados para hacer una trisección y dejando $r = n - (h + x + y)$ nodos que no están en el subárbol pesado o en $x$ o $y$ . $$h(r+x)y \ge (h+r)xy$$ $$h(r+x) \ge (h+r)x$$ $$hr + hx >= hx + rx$$ $$hr >= rx$$ $$h >= x $$

Dado que elegimos específicamente $h \ge$ todos los valores posibles de $x$ podemos contar con poder encontrar una trisección óptima limitándonos a trisecciones que incluyan al menos $1$ corte en el subárbol pesado. (Obsérvese que $y$ se elimina por completo de la ecuación, por lo que no importa si $x$ es mayor o menor que $y$ lo que significa que no tenemos que preocuparnos de que $y$ puede ser un subárbol de $x$ . Si $y$ era un subárbol de $x$ , lo que nos impide mantener $y$ mientras se sustituye $x$ con $h$ Podríamos sustituir $y$ con $h$ en su lugar).

Por un razonamiento similar a los argumentos de bisección y trisección anteriores, también podemos estar seguros de que si la trisección óptima requiere 2 cortes en el subárbol pesado, entonces será la bisección óptima del subárbol pesado cortada del resto del árbol. Si se hace $2$ cortes en el subárbol pesado, se está comprometiendo a $r \ge n/2$ ser $a$ el mayor de los 3 componentes de la trisección. Con $r > n/3$ quieres hacerlo más pequeño, por lo que quieres $b+c$ sea lo más grande posible, lo que significa que se quiere un corte entre el subárbol pesado y la raíz. Con esto hecho y el requisito de que el segundo corte esté en el subárbol pesado, el mejor segundo corte es por definición la bisección óptima del subárbol pesado.

Molerlo todo

Una vez establecido esto, sólo necesitamos algunas estructuras de datos sencillas. Ya hemos encontrado todos los tamaños de subárbol posibles para el árbol completo. Podemos encontrar todos los cortes posibles en el subárbol pesado y la mejor bisección del subárbol pesado en $O(n)$ .

Podemos entonces poner los tamaños de todos los subárboles que no están en el subárbol pesado en un árbol de búsqueda binario en $O(n \log n)$ . Entonces, dado un corte en el subárbol pesado, podemos encontrar el mejor corte posible que no esté en el subárbol pesado en $O(\log n)$ tiempo.

A continuación, probamos todos los $O(n)$ cortes del subárbol pesado contra todos los cortes que no están en el subárbol pesado para $O(n \log n)$ tiempo total de funcionamiento.

Luego hemos calculado todas las posibles trisecciones que no hemos descartado, y si estábamos atentos, recordamos cuál era $max(abc)$ . Hemos terminado.

Optimización para $O(n)$ tiempo total de funcionamiento

Si realmente nos importa la complejidad temporal de esto, podemos deshacernos de las ordenaciones y las búsquedas binarias a costa de aumentar el número de $O(n)$ operaciones y haciendo que la solución sea aún más molesta.

Podemos, en una $O(n)$ pasar por la estructura de datos, encontrar cualquier número que constituya la "mejor" elección según algún criterio arbitrario, siempre y cuando siempre haya una "mejor" elección o no nos importe cuál de varias elecciones igualmente buenas elegimos como "mejor", que es nuestro caso.

Dividamos el árbol completo $T$ de tamaño $n$ en el subárbol pesado $H$ y el resto del árbol $R$ . Utilizando el análisis que nos llevó a la $O(n \log n)$ solución, sólo necesitamos encontrar 10 números. Utilizaré la abreviatura "par más cercano a x" para referirme al par de números formado por el número más pequeño $\ge x$ y el mayor número $\le x$ aunque, por supuesto, los 2 números más cercanos a $x$ puede ser mayor o menor que $x$ .

• $h = |H|$ el peso de $H$
• $h_{half}$ el peso del subárbol de $H$ más cercano a $h \over 2$
• 2 pesos de los subárboles de $H$ el par más cercano a $n \over 3$ .
• 2 pesos de los subárboles de $R$ el par más cercano a $n \over 3$
• 2 pesos de los subárboles de $H$ : Para cada uno de los pesos $w$ del par de subárboles en $R$ más cercano a $n \over 3$ el peso del subárbol más cercano a $(n-w)\over 2$
• 2 pesos de los subárboles de $R$ : Para cada uno de los pesos $w$ del par de subárboles en $H$ más cercano a $n \over 3$ el peso del subárbol más cercano a $(n-w)\over 2$

La mejor trisección va a ser $h_{half}(h - h_{half})(n-h)$ o alguna combinación de 1 de los 4 subárboles de $H$ con 1 de los 4 subárboles de $R$ encontrado arriba. Como algunos de los subárboles podrían ser iguales (y lo sabríamos enseguida), no necesitamos necesariamente encontrar los 10 números. Podríamos salirnos con la suya encontrando sólo $h$ y 2 subárboles de peso exacto $n\over 3$ y no tener que buscar más. Así que encontramos de 3 a 10 números para hacer de 1 a 1+4+4 = 9 posibles particiones para intentar elegir la mejor, todo $O(n)$ o $O(1)$ operaciones, y tenemos y respuesta en $O(n)$ tiempo.

Glosario

• Un árbol jerárquico de tamaño o peso $n$ = un gráfico de árbol $G = (V,E)$ de orden $n$
• es una colección de $n$ nodos = $|G|$ = $|V|$ vértices (singular: vértice) conectados por
• $n-1$ conexiones = $|V|-1$ bordes = $|E|$ bordes,
• de tal manera que cada nodo es alcanzable = conectado a cada otro nodo por un único camino, lo que significa que no hay
• nodos con más de un padre = ciclos.
• El $order$ de un componente o un gráfico es el número de vértices que contiene.
• El $degree$ de un nodo/vértice es el número de conexiones al nodo = aristas que tienen el vértice como punto final.
• El $weight$ de un nodo en un árbol jerárquico es el número de nodos del subárbol rooteado en ese nodo, que es igual al número de descendientes del nodo más $1$ para el propio nodo.
• Algo es más pesado que otra cosa si tiene mayor peso. Del mismo modo, se dice que algo con menos peso es más ligero.
• Un componente es un grafo conectado máximo = un conjunto de vértices tal que hay un camino desde cualquier vértice a cualquier otro vértice. Un grafo en forma de árbol es un tipo especial de grafo que es un componente único sin ciclos ni aristas paralelas. Tiene el mínimo número de aristas posible para que los vértices sean un único componente (completamente conectado).
• Un árbol jerárquico es una especialización de un gráfico de árbol. Tiene un único nodo designado como raíz. Todos los nodos, excepto la raíz, tienen exactamente $1$ padre. (La raíz no tiene un padre). Todos los nodos conectados a un nodo, excepto su padre, se dicen hijos de ese nodo y tienen ese nodo como padre. Así, para todos los nodos, si $a$ es $b$ de los padres, $b$ es $a$ y todos los nodos conectados a la raíz son hijos de la misma. Se dice que los hijos están por debajo de sus padres y que los padres están por encima de sus hijos. Todos los hijos de un nodo determinado se llaman hermanos entre sí. Los hijos de un nodo se denominan nietos, y para describir el resto de las relaciones se utilizan nombres coherentes con la genealogía, con la salvedad de que un nodo sin hijos se denomina hoja. Los descendientes de un nodo son sus hijos y todos sus descendientes.
• Un subárbol de un árbol es un árbol propiamente dicho, formado por un nodo y todos sus descendientes. El subárbol correspondiente al nodo raíz es el árbol completo.
• Un gráfico de árbol puede tener su raíz en un vértice. Cualquier nodo/vértice puede ser elegido como raíz.
• Para rootear un gráfico de árbol en un vértice $r$ significa mapearlo en un árbol jerárquico con $r$ como raíz, todos los vecinos de $r$ como hijos de la raíz y todos sus padres la raíz, y luego recursivamente para cada vértice $v$ empezando por los hijos de la raíz, designando a los vecinos de $v$ excepto su padre como sus hijos y designando al padre de sus hijos como $v$ , recurriendo a $v$ hasta que todos los vértices estén mapeados. Al final, cada vértice del grafo del árbol corresponde exactamente a 1 nodo del árbol, y cada arista del grafo del árbol corresponde exactamente a 1 conexión padre-hijo, por lo que pueden considerarse intercambiables.
• Cuando se desconecta un nodo de su padre, se dice que se convierte en la raíz de un subárbol disjunto, y se puede denominar el subárbol rooteado en ese nodo.
• Del mismo modo, cuando se corta una arista de un gráfico de árbol, se divide (o $bisect$ ) en $2$ gráficos de árbol, uno que contiene los vértices que permanecen conectados al vértice de un lado de la arista (y todas las aristas que los conectan) y los que permanecen conectados al vértice del otro lado de la arista (y todas las aristas que los conectan). Esto se llama $bisection$ . Eliminar $2$ bordes y tú $trisect$ el árbol (a $trisection$ ).
• Un nodo sin hijos no tiene descendientes y se llama hoja. Un vértice de grado $1$ se llama hoja. Es posible rootear un gráfico de árbol en un vértice de grado $1$ pero en un árbol jerárquico la raíz no se considera una hoja a menos que sea el único nodo del árbol.

Answer 2

Encontrar un vértice $r$ de manera que los componentes de $G-r$ todos tienen un orden como máximo $n/2.$ Denotemos estos componentes por $T_i$ para $1\leq i\leq k,$ con $|T_1|\geq |T_2|\geq |T_3|\geq\cdots.$ Mediante la recursión en estos árboles podemos calcular eficazmente el conjunto $S_i$ de posibles cardinalidades $|T'|$ de conjuntos $T'\subseteq T_i$ tal que $T'$ y $G\setminus T'$ están conectados.

La trisección tendrá $r\in A.$ Voy a considerar varios casos para $B$ y $C,$ que son exhaustivos hasta la permutación $A,B,C.$ En cada caso, el algoritmo debe encontrar una trisección óptima sujeta a la restricción para ese caso.

1. $B$ y $C$ ambos se encuentran en algún $T_i.$

   Siempre es mejor hacer $A\cap T_i$ lo más pequeño posible porque $(a-1)(b+1)c\geq abc$ para $a\geq n/2>b,c.$ Así que sólo tenemos que comprobar el caso $A\cap T_i=\emptyset,$ o, en otras palabras, cuando $B,C$ son una bisección óptima de $T_i.$ Esto se puede encontrar en el tiempo $O(|T_i|).$

2. $B$ y $C$ se encuentran en diferentes $T_i$ 's, y $b,c\leq n/3$

   En este caso debemos elegir $b$ y $c$ tan grande como sea posible sin exceder $n/3,$ porque $c\leq n/3$ y $b<b'\leq n/3$ implica $(n-b-c)bc \leq (n-b'-c)b'c.$ Entre los $k$ valores $\max(S_i\cap \{1,\dots,\lfloor n/3\rfloor\}),$ tomando los dos primeros da valores para $b$ y $c$ ; mira el correspondiente $T_i$ para ver de qué trisección viene esto.

3. $B$ y $C$ se encuentran en diferentes $T_i$ 's, y $b,c\geq n/3$

   Sólo tenemos que comprobar el caso $B\subseteq T_1$ y $C\subseteq T_2$ porque el otro $T_i$ son demasiado pequeños. Elige $b$ y $c$ lo más pequeño posible, para que $b=S_1\cap\{\lceil n/3\rceil,\dots\}$ y de manera similar para $c,$ y resolver a qué trisección corresponde.

4. $B$ y $C$ se encuentran en diferentes $T_i$ 's, y $b\geq n/3$ y $c\leq n/3$

   Dividido en casos para $1\leq i\leq 2.$ Para cada caso queremos encontrar el máximo de $(n-b-c)bc$ en $b\in S_i$ y $c\in S_i'$ donde $S_i'=\bigcup_{j\neq i}S_j.$ Esto puede hacerse de forma eficiente, por ejemplo, clasificando $S'_i$ y entonces para cada $b$ encontrar el $c\in S'_i$ tan cerca de $(n-b)/2$ como sea posible utilizando una búsqueda binaria. (Debería ser posible optimizar esto a un tiempo lineal: como $b$ aumenta, el óptimo $c$ disminuye o se mantiene igual).

Answer 3

Creo que se puede utilizar la descomposición ligera pesada para obtener una $\mathcal{O}(n\log^2n)$ algoritmo de tiempo. Esto es bastante complicado, así que no me molestaré en dar demasiados detalles. La idea es la siguiente.

Fijar alguna raíz y determinar el HLD. Luego, para cada nodo, consideramos el subárbol rooteado en ese nodo. A estos subárboles los llamaremos subárboles enraizados. Podemos hacer fácilmente una DFS en tiempo lineal para determinar para cada subárbol rooteado cuántos nodos contiene. Menos obvio es que entonces podemos hacer un $\mathcal{O}(n\log^2n)$ tiempo DFS en todas las cadenas pesadas para determinar para cada subárbol rooteado el óptimo $2$ -de ese subgrafo. Con toda esta información procesada, podemos encontrar el óptimo $3$ -de la gráfica original en $\mathcal{O}(n\log^2n)$ tiempo.

El DFS en las cadenas pesadas funciona como sigue. Para cada cadena, trabajamos de abajo a arriba. Podemos llevar la cuenta de todos los tamaños de los subárboles enraizados por debajo del nodo actual en un BST. Así, para cada nodo $N$ en la cadena pesada, de abajo a arriba, añadimos todos los tamaños de los subárboles enraizados de sus descendientes que no estén ya en el BST (éstos pueden encontrarse fácilmente en tiempo lineal con un DFS), y luego hacemos una consulta para encontrar el tamaño más cercano a $s/2$ donde $s$ es el tamaño del subárbol rooteado de $N$ . Dado que cada camino desde una raíz a un nodo interseca $\mathcal{O}(\log n)$ cadenas pesadas, cada nodo sólo se considera $\mathcal{O}(\log n)$ tiempos. Hay $n$ tales nodos y las operaciones BST cuestan $\mathcal{O}(\log n)$ tiempo, por lo que este paso lleva $\mathcal{O}(n\log^2n)$ tiempo en total.

Por último, encontrar el óptimo $3$ -de la gráfica original en $\mathcal{O}(n\log^2n)$ tiempo sigue siendo bastante tedioso. Cualquier $3$ -corte es en sí mismo un gráfico de árbol, cuando conectamos dos componentes si están conectados en el gráfico original. Obsérvese que sólo hay un grafo arbóreo posible con $3$ nodos. La raíz de nuestro gráfico original estará en un componente. Podemos considerar dos casos. El componente raíz está conectado a los otros dos componentes, o sólo a uno.

Si el componente raíz está conectado a un solo componente, podemos considerar simplemente todos los posibles subárboles enraizados y sus óptimos $2$ -Corte. Entonces encontrará el óptimo $3$ -corte en el que el componente raíz está conectado sólo a otro componente. Esto requiere un tiempo lineal.

Si el componente raíz está conectado a los otros dos componentes, las cosas se complican mucho más y tendremos que volver a utilizar nuestro HLD. Para este paso necesitamos un BST global. Inicialmente contiene todos los tamaños de subárboles enraizados. Para cada cadena pesada, trabajamos de abajo a arriba. Queremos considerar para cada nodo de la cadena el óptimo $3$ -corte donde uno de los componentes es su subárbol rooteado. Esto significa que el otro componente que no contiene la raíz debe ser un subárbol rooteado disjunto. Por lo tanto, queremos llevar la cuenta de todos esos subárboles enraizados en nuestro BST.

Si recorremos las cadenas pesadas en un DFS, podemos asegurarnos de que cada subárbol rooteado que contenga la cadena pesada actual ya está eliminado del BST. A continuación, trabajando de abajo a arriba, podemos asegurarnos de que cada subárbol rooteado por debajo del nodo actual también se elimina del BST. A continuación, podemos hacer un $\mathcal{O}(\log n)$ Consulta del BST para encontrar el $3$ -cortada por el nodo. Por último, añadimos todos los subárboles enraizados al BST. Por un análisis similar al anterior, este paso llevará $\mathcal{O}(n\log^2n)$ tiempo en total.