Ce document investigate la complexité du calcul et de l'approximation de la profondeur d'arbre, un paramètre fondamental en théorie algorithmique des graphes. Les auteurs présentent plusieurs résultats de difficulté et des bornes inférieures, éclairant la difficulté intrinsèque de ce problème.
**Points clés** :
* **Profondeur d'arbre et Couverture de sommets** : Le document établit une connexion entre la profondeur d'arbre et la couverture de sommets dans les graphes tripartites. En construisant un supergraphe d'un graphe tripartite donné, les auteurs montrent que la profondeur d'arbre du supergraphe est étroitement contrôlée par le nombre de couverture de sommets du graphe original. Ce résultat permet de dériver des bornes inférieures sur la profondeur d'arbre basées sur des résultats de difficulté connus pour la couverture de sommets.
* **Difficulté NP du Problème d'Approximation** : Les auteurs prouvent que c'est NP-difficile d'approximer la profondeur d'arbre dans un facteur de 1.0003. Ce résultat exclut l'existence d'un algorithme d'approximation en temps polynomial (PTAS) pour la profondeur d'arbre à moins que P = NP.
* **Bornes Inférieures Basées sur l'Hypothèse du Temps Exponential (ETH)** : En supposant l'ETH, les auteurs montrent qu'il existe une constante absolue ε > 0 telle que la profondeur d'arbre d'un graphe à n sommets ne peut pas être calculée en temps O(2^εn). Ce résultat exclut l'existence d'algorithmes exacts paramétrisés en temps 2^o(k) n^O(1) pour la profondeur d'arbre sous l'ETH.
* **Bornes Inférieures sur la Complexité d'Approximation** : Les auteurs dérivent également que tout algorithme d'approximation (1 + δ) pour la profondeur d'arbre nécessite un temps 2^Ω(n/ log n) sous l'ETH. Ce résultat fournit une borne inférieure sur la complexité temporelle de l'approximation de la profondeur d'arbre à un facteur constant petit.
**Contributions Techniques** :
* **Réduction de la Satisfaisabilité à la Profondeur d'Arbre** : Les auteurs conçoivent une réduction linéaire simple de la problème de satisfaisabilité à la profondeur d'arbre. Cette réduction est inspirée d'un résultat récent pour la largeur d'arbre et repose sur la difficulté de la couverture de sommets sur les graphes tripartites.
* **Construction de Graphes Tripartites** : Les auteurs construisent un graphe tripartite dont la profondeur d'arbre dépend du nombre maximum de clauses pouvant être satisfaites dans une formule k-CNF donnée. Cette construction est utilisée pour dériver les résultats de difficulté et les bornes inférieures mentionnés précédemment.
**Implications** :
Les résultats présentés dans ce document fournissent des insights précieux sur la complexité du calcul et de l'approximation de la profondeur d'arbre. Ils montrent la difficulté intrinsèque de ce problème et suggèrent que des algorithmes efficaces pour la profondeur d'arbre pourraient être difficiles à obtenir. Les résultats ont également des implications pour l'étude d'autres paramètres et algorithmes de graphes liés à la profondeur d'arbre.