Este documento investiga la complejidad de calcular y approximar la profundidad de árbol, un parámetro fundamental en la teoría de grafos algorítmica. Los autores presentan varios resultados de dificultad y límites inferiores, iluminando la dificultad inherente de este problema.
**Puntos Clave**:
* **Profundidad de Árbol y Cubrimiento de Vértices**: El documento establece una conexión entre la profundidad de árbol y el cubrimiento de vértices en grafos tripartitos. Al construir un supergrafo de un grafo tripartito dado, los autores demuestran que la profundidad de árbol del supergrafo está estrictamente controlada por el número de cubrimiento de vértices del grafo original. Este resultado permite derivar límites inferiores sobre la profundidad de árbol basados en resultados de dificultad conocidos para el cubrimiento de vértices.
* **Dificultad NP de la Aproximación**: Los autores prueban que es NP-difícil approximar la profundidad de árbol dentro de un factor de 1.0003. Este resultado descarta la existencia de un esquema de aproximación polinomial (PTAS) para la profundidad de árbol a menos que P = NP.
* **Límites Inferiores bajo la Hipótesis del Tiempo Exponencial (ETH)**: Suponiendo la ETH, los autores muestran que existe un constante absoluta ε > 0 tal que la profundidad de árbol de un grafo con n vértices no puede ser computada en tiempo O(2^εn). Este resultado excluye la existencia de algoritmos exactos parametrizados de tiempo 2^o(k) n^O(1) para la profundidad de árbol bajo la ETH.
* **Límites Inferiores de Complejidad de Aproximación**: Los autores derivan además que cualquier algoritmo de aproximación (1 + δ) para la profundidad de árbol requiere tiempo 2^Ω(n/ log n) bajo la ETH. Este resultado proporciona un límite inferior sobre la complejidad de tiempo de la aproximación de la profundidad de árbol a un factor constante pequeño.
**Contribuciones Técnicas**:
* **Reducción desde Satisfactibilidad a Profundidad de Árbol**: Los autores diseñan una reducción lineal simple desde el problema de satisfactibilidad a la profundidad de árbol. Esta reducción está inspirada en un resultado reciente para la anchura de árbol y se basa en la dificultad del cubrimiento de vértices en grafos tripartitos.
* **Construcción de Grafos Tripartitos**: Los autores construyen un grafo tripartito cuyas profundidad de árbol depende del número máximo de cláusulas que pueden satisfacerse en una fórmula k-CNF dada. Esta construcción se utiliza para derivar los resultados de dificultad y los límites inferiores mencionados anteriormente.
**Implicaciones**:
Los resultados presentados en este documento proporcionan valiosas insinuaciones sobre la complejidad de calcular y approximar la profundidad de árbol. Demuestran la dificultad inherente de este problema y sugieren que los algoritmos eficientes para la profundidad de árbol pueden ser desafiantes de lograr. Los resultados también tienen implicaciones para el estudio de otros parámetros de grafos y algoritmos relacionados con la profundidad de árbol.