Existe-t-il des classes de graphiques intéressantes où la largeur de l'arborescence est difficile (facile) à calculer?

Treewith est un paramètre de graphique important qui indique à quel point un graphique est proche d'être un arbre (bien que pas dans un sens topologique strict).

Il est bien connu que le calcul de la largeur d'arbre est NP-difficile.

Existe-t-il des classes naturelles de graphiques où la largeur d'arbre est difficile à calculer?

De même:

Existe-t-il des classes de graphes intéressantes où le calcul de la largeur d'arbre est facile? Si oui, existe-t-il des propriétés / tests structurels pouvant être exploités? -À- dire, le graphique a la propriété X ⇒ le calcul de la largeur arborescente de G ∈ P .$G$$X$ $\Rightarrow$$G \in \mathbf{P}$

La largeur d'arbre est NP-difficile à calculer sur des graphiques co-bipartis, en effet la preuve originale de dureté NP de la largeur d' arbre d'Arnborg et al. montre cela. De plus, Bodlaender et Thilikos ont montré qu'il est difficile de calculer la largeur d'arbre des graphiques de degré maximum . Enfin, pour tout graphique de largeur d'arbre au moins 2 , la subdivision d' un bord (c'est-à-dire le remplacement du bord par un sommet de degré 2 adjacent aux deux extrémités du bord) ne change pas la largeur d'arbre du graphique. Par conséquent, il est difficile de calculer la largeur d'arbre de graphes bipartites à 2 dégénérés de circonférence arbitrairement grande.$9$$2$$2$

Le problème est le temps polynomial résoluble sur les graphes en accords, les graphes de permutation, et plus généralement sur toutes les classes de graphes avec un nombre polynomial de cliques maximales potentielles, voir cet article de Bouchitte et Todinca. Notez que dans le même article, il est montré que l'ensemble des cliques maximales potentielles d'un graphe G peut être calculé à partir de G dans le temps O ( | Π ( G ) | 2 ⋅ n O ( 1 ) ) . De plus, l'algorithme de Bodlaender détermine si $\Pi(G)$$G$$G$$O(|\Pi(G)|^2 \cdot n^{O(1)})$$G$a une largeur d'arbre au plus dans le temps 2 O ( k 3 ) n . Par conséquent, treewidth est résoluble en temps polynomial pour les graphes de largeur arborescente O ( ( log n ) 1 / 3 ) .$k$$2^{O(k^3)}n$$O((\log n)^{1/3})$

Il s'agit d'un problème ouvert en suspens, que le calcul de la largeur d'arbre des graphes planaires soit résolu dans le temps polynomial ou NP complet. Il convient de noter que la largeur de branche du paramètre de graphique connexe (qui est toujours dans un facteur 1,5 de la largeur d'arbre) est le temps polynomial calculable sur les graphiques planaires.