Fazendo uma decomposição de árvore de largura mínima se inclinar em tempo polinomial

Como é sabido, uma decomposição em árvore de um gráfico consiste em uma árvore com uma bolsa associada para cada vértice , que satisfaz as seguintes condições:T T v ⊆ V ( G ) v ∈ V ( T $G$$T$$T_v \subseteq V(G)$$v \in V(T)$

1. Cada vértice de ocorre em algum saco de .$G$$T$
2. Para cada extremidade de há uma bolsa contendo os dois pontos finais da borda.$G$
3. Para cada vértice , os sacos que contêm induzir uma sub-árvore ligado de .v $v \in V(G)$$v$$T$

Também podemos exigir a seguinte condição, chamada magreza , de nossa decomposição:

• Para cada par de malas , de , se e com , então a) existem caminhos separados por vértices em ou b) a árvore contém uma aresta no caminho do nó ao nó modo que e o conjunto intersecta todas caminhos em .$T_a$$T_b$$T$$A \subseteq T_a$$B \subseteq T_b$$|A| = |B| = k$$k$$A-B$$G$$T$$pq$$a$$b$$|V(T_p) \cap V(T_q)| \leq k$$V(T_p) \cap V(T_q)$$A-B$$G$

Robin Thomas mostrou que sempre há uma decomposição de árvores de largura mínima, que também é enxuta, e provas mais simples desse fato foram fornecidas por vários autores, por exemplo, por Patrick Bellenbaum e Reinhard Diestel .

O que me interessa é o seguinte: dado um gráfico e uma decomposição de árvore com largura mínima de , podemos encontrar uma decomposição de árvore magra com largura mínima de em tempo polinomial?$G$$G$$G$

As duas provas mencionadas não produzem uma construtividade tão eficiente. No artigo de Bellenbaum e Diestel, é mencionado que "Outra prova curta (mais construtiva) do teorema de Thomas foi apresentada em P. Bellenbaum, Schlanke Baumzerlegungen von Graphen, Diplomarbeit, Universitat Hamburg 2000". Infelizmente, não consegui encontrar o manuscrito on-line e meu alemão não é tão bom assim.

Aqui está uma razão formal pela qual o problema não pode ser resolvido em poli-tempo, a menos que P = NP. Sabemos que encontrar a largura da árvore de um determinado gráfico é NP-Hard. Dado um gráfico , podemos adicionar um clique separado do tamanho V ( G ) + 1 para criar um novo gráfico G ′ . Uma árvore de decomposição-min-largura de G ' pode ser obtido como se segue: tem dois nodos com um saco contendo todos os nós da clique e o outro contendo todos os nós de L . Agora a fazer esta árvore-decomposição magra seria necessário encontrar uma decomposição lean-árvore do grafo original G que, como um subproduto, dar o treewidth de G .$G$$V(G)+1$$G'$$G'$$G$$G$$G$