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

16

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 vV ( G ) v V ( T )GTTvV(G)vV(T)

  1. Cada vértice de ocorre em algum saco de .TGT
  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 TvV(G)vT

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 .TaTbTATaBTb|A|=|B|=kkABGTpqab|V(Tp)V(Tq)|kV(Tp)V(Tq)ABG

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?GGG

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.

Bart Jansen
fonte
2
Boa pergunta. Encontrar uma decomposição de árvore de largura mínima é NP-Hard, portanto, o seu problema está um pouco incorreto (parece). Meu palpite seria que se pode pedir isso para um caso de largura de árvore limitada ou no sentido de aproximação.
Chandra Chekuri
11
Mas, no caso dele, ele recebeu uma decomposição de árvore de largura mínima e deseja um algoritmo para torná-lo mais enxuto.
Suresh Venkat
11
@SureshVenkat: Sei que ele recebe uma decomposição de árvores com largura mínima, mas como você pode verificar se está correta? Além disso, uma decomposição de árvore magra se adapta localmente à largura da árvore de diferentes partes do gráfico, portanto, a decomposição em árvore do gráfico global que é ideal não evita o problema de encontrar a largura da árvore das peças locais que é difícil.
Chandra Chekuri 02/12/19
Decomposições de árvores suaves (onde todos os sacos têm o mesmo tamanho e dois sacos adjacentes diferem exatamente por um vértice) são muito mais fáceis de manusear do que as decomposições gerais de árvores, e é fácil ver que sempre há uma decomposição de árvores de largura mínima que é suave . Portanto, talvez você possa obter uma construção eficiente restringindo uma das construções conhecidas a elas. Sempre existe uma decomposição de árvores de largura mínima que é suave e esbelta?
Diego de Estrada
11
@ChandraChekuri Presumo que o problema de verificação seja resolvido se você o considerar um problema promissor, mas entendo o seu ponto de decompor uma árvore, não necessariamente fornecendo informações suficientes para você se adaptar. Mas a seguinte pergunta pode ser plausível: existe uma maneira de "localmente" modificar uma determinada decomposição de árvore para torná-la "enxuta" sem aumentar a largura da árvore?
Suresh Venkat

Respostas:

8

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 .GV(G)+1GGGGG

Chandra Chekuri
fonte
11
Bom ponto. Você sabe se alguma coisa é conhecida sobre algoritmos de tempo parametrizados e / ou moderadamente exponenciais para encontrar decomposições de árvores enxutas?
Bart Jansen