Hacer que una descomposición de árbol de ancho mínimo se apoye en tiempo polinómico

Como es bien sabido, la descomposición de un árbol de un gráfico consiste en un árbol T con una bolsa asociada T v ⊆ V ( G ) para cada vértice , que cumple las siguientes condiciones:$G$$T$$T_v \subseteq V(G)$$v \in V(T)$

1. Cada vértice de se produce en alguna bolsa de .$G$$T$
2. Para cada borde de hay una bolsa que contiene ambos puntos finales del borde.$G$
3. Para cada vértice , las bolsas que contienen inducen un subárbol conectado de .$v \in V(G)$$v$$T$

También podemos exigir la siguiente condición, llamada delgadez , de nuestra descomposición:

• Por cada par de bolsas , de$T_a$$T_b$ , si A ⊆ T a y B ⊆ T b con | A | = | B | = k , entonces a) hay k vértices disjuntos A - B caminos en G , o b) el árbol T contiene un borde p q en el camino del nodo a al nodo b tal que | V ( T $T$$A \subseteq T_a$$B \subseteq T_b$$|A| = |B| = k$$k$$A-B$$G$$T$$pq$$a$$b$ y el conjunto V ( T p ) ∩ V ( T q ) intersecta todos A - B caminos en G .$|V(T_p) \cap V(T_q)| \leq k$$V(T_p) \cap V(T_q)$$A-B$$G$

Robin Thomas demostró que siempre hay una descomposición del árbol de ancho mínimo, que también es delgada, y varios autores han proporcionado pruebas más simples de este hecho, por ejemplo, Patrick Bellenbaum y Reinhard Diestel .

Lo que me interesa es lo siguiente: dado un gráfico y una descomposición de árbol de ancho mínimo de G , ¿podemos encontrar una descomposición de árbol magro de ancho mínimo de G en tiempo polinomial?$G$$G$$G$

Las dos pruebas mencionadas no producen una constructividad tan eficiente. En el artículo de Bellenbaum y Diestel se menciona que "se ha proporcionado otra prueba breve (más constructiva) del teorema de Thomas en P. Bellenbaum, Schlanke Baumzerlegungen von Graphen, Diplomarbeit, Universitat Hamburg 2000." Por desgracia, no he podido encontrar el manuscrito en línea y mi alemán no es tan bueno.

Aquí hay una razón formal por la cual el problema no puede resolverse en el tiempo múltiple a menos que P = NP. Sabemos que encontrar el ancho de árbol de un gráfico dado es NP-Hard. Dado un gráfico , podemos agregar una camarilla disjunta de tamaño V ( G ) + 1 para crear un nuevo gráfico G ' . A-min anchura árbol-descomposición de G ' se puede obtener como sigue: tiene dos nodos con una bolsa que contiene todos los nodos de la camarilla y el otro que contiene todos los nodos de G . Haciendo ahora este árbol-descomposición magra requeriría encontrar una descomposición magra-árbol del gráfico original G , que sería, como un subproducto, dar el treewidth de G .$G$$V(G)+1$$G'$$G'$$G$$G$$G$