¿Hay clases de gráficos interesantes donde el ancho del árbol es difícil (fácil) de calcular?

Treewith es un parámetro gráfico importante que indica qué tan cerca está un gráfico de ser un árbol (aunque no en un sentido topológico estricto).

Es bien sabido que calcular el ancho de árbol es NP-hard.

¿Hay clases naturales de gráficos donde el ancho del árbol es difícil de calcular?

Similar:

¿Hay clases de gráficos interesantes donde el cálculo del ancho de árbol es fácil? En caso afirmativo, ¿hay alguna propiedad / prueba estructural que pueda explotarse? Es decir, el Gráfico tiene la propiedad calculando el ancho de árbol de .X ⇒ G ∈ $G$$X$ $\Rightarrow$$G \in \mathbf{P}$

Treewidth es NP-difícil de calcular en gráficos co-bipartitos, de hecho, la prueba de dureza NP original del ancho de árbol de Arnborg et al. muestra esto Además, Bodlaender y Thilikos demostraron que es NP-difícil calcular el ancho de árbol de los gráficos de grado máximo . Finalmente, para cualquier gráfico de ancho de árbol de al menos 2 , subdividir un borde (es decir, reemplazar el borde por un vértice de grado 2 adyacente a los dos extremos del borde) no cambia el ancho de árbol del gráfico. Por lo tanto, es NP-difícil calcular el ancho de árbol de gráficos bipartitos de 2 degenerados de circunferencia arbitrariamente grande.$9$$2$$2$

El problema es el tiempo polinómico que se puede resolver en gráficos cordales, gráficos de permutación y, más generalmente, en todas las clases de gráficos con un número polinómico de camarillas máximas potenciales, consulte este documento de Bouchitte y Todinca. Tenga en cuenta que en el mismo documento se muestra que el conjunto de posibles camarillas máximas de un gráfico G se puede calcular a partir de G en el tiempo O ( | tiene un ancho de árbol como máximo k en el tiempo 2 O ( k $\Pi(G)$$G$$G$ . Además,el algoritmo de Bodlaenderdetermina si$O(|\Pi(G)|^2 \cdot n^{O(1)})$$G$$k$. Por lo tanto, treewidth es resoluble tiempo polinómico para gráficos de treewidthO((logn ) 1 / 3 ).$2^{O(k^3)}n$$O((\log n)^{1/3})$

Es un problema abierto sobresaliente si calcular el ancho de árbol de los gráficos planos es polinomial solucionable en tiempo o NP completo. Vale la pena señalar que el ancho de rama del parámetro gráfico correspondiente (que siempre está dentro de un factor de 1.5 del ancho del árbol) es un tiempo polinómico computable en gráficos planos.