Existem classes de gráficos interessantes em que a largura da árvore é difícil (fácil) de calcular?

Treewith é um parâmetro importante do gráfico que indica o quão perto um gráfico está de ser uma árvore (embora não em um sentido topológico estrito).

É sabido que calcular a largura da árvore é difícil para NP.

Existem classes naturais de gráficos em que a largura da árvore é difícil de calcular?

Similarmente:

Existem classes de gráficos interessantes em que o cálculo da largura da árvore é fácil? Em caso afirmativo, existe alguma propriedade / teste estrutural que possa ser explorado? Ou seja, Gráfico tem propriedade X ⇒ calcular o treewidth de L ∈ P .$G$$X$ $\Rightarrow$$G \in \mathbf{P}$

A largura de árvore é NP-difícil de calcular em gráficos co-bipartidos, na verdade a prova de dureza NP original da largura de árvore de Arnborg et al. mostra isso. Além disso, Bodlaender e Thilikos mostraram que é NP-difícil calcular a largura de árvore dos gráficos de grau máximo . Finalmente, para qualquer gráfico de largura da árvore pelo menos 2 , subdividir uma aresta (ou seja, substituir a aresta por um vértice de grau 2 adjacente aos dois pontos finais da aresta) não altera a largura da árvore do gráfico. Portanto, é NP-difícil calcular a largura da árvore de gráficos bipartidos 2-degenerados de perímetro arbitrariamente grande.$9$$2$$2$

O problema é o tempo polinomial solucionável em gráficos de acordes, gráficos de permutação e mais geralmente em todas as classes de gráficos com um número polinomial de possíveis cliques máximos, veja este artigo de Bouchitte e Todinca. Observe que no mesmo trabalho é mostrado que o conjunto de possíveis cliques máximos de um gráfico G pode ser calculado a partir de G no tempo O ( | Π ( G ) | 2 ⋅ n O ( 1 ) ) . Além disso, o algoritmo de Bodlaender determina se $\Pi(G)$$G$$G$$O(|\Pi(G)|^2 \cdot n^{O(1)})$$G$tem uma largura de árvore no máximo no tempo 2 O ( k 3 ) n . Por isso, é solúvel treewidth tempo polinomial para gráficos de treewidth O ( ( log n ) 1 / 3 ) .$k$$2^{O(k^3)}n$$O((\log n)^{1/3})$

É um problema pendente em aberto se o cálculo da largura de árvore dos gráficos planares é solucionável em tempo polinomial ou em NP completo. Vale a pena notar que o parâmetro do gráfico relacionado branchwidth (que está sempre a um fator a 1,5 da largura da árvore) é um tempo polinomial computável em gráficos planares.