Largura e embalagem das árvores

Minha pergunta é um pouco vaga. Fiquei me perguntando se (e como), podemos aplicar a noção de largura de árvore aos problemas de empacotamento em gráficos.

Eu ficaria feliz com quaisquer insights ou referências de trabalhos de pesquisa anteriores sobre isso (assumindo que há alguma relação). Obrigado.

Eu posso interpretar essa pergunta de duas maneiras diferentes:

1) Quando se trata de propriedades algorítmicas de problemas de empacotamento em gráficos de largura de árvore limitada, o Teorema de Courcelle mostra que, para cada fixo , podemos resolver de maneira ideal problemas expressáveis ​​na lógica monádica de segunda ordem em tempo linear em gráficos de largura de árvore no máximo (veja, por exemplo, http://dx.doi.org/10.1093/comjnl/bxm037$k$$k$para uma pesquisa sobre as propriedades algorítmicas dos gráficos de largura de árvore delimitada). Como muitos problemas de empacotamento podem ser formulados no MSOL, isso prova a rastreabilidade de muitos desses problemas em gráficos de largura de árvore limitada, incluindo Conjunto Independente, Empacotamento Triangular, Empacotamento de Ciclo, cópias separadas de vértice / aresta de qualquer gráfico fixo, modelos menores de vértice e disjunção de algum gráfico fixo H e assim por diante. Porém, como essa capacidade de extensão se estende a todos os problemas definíveis pelo MSOL, ela não é específica para o empacotamento.

2) Quando se trata de relações gráfico-estruturais entre embalagens e largura de árvore, o seguinte pode ser interessante. Graças ao trabalho de Robertson e Seymour, sabe-se que existe uma função modo que todo gráfico de largura de árvore pelo menos contenha uma grade como menor de idade (o limite original de fornecido por Seymour e Robertson foi posteriormente aprimorado em colaboração com Thomas; consulte http://www.sciencedirect.com/science/article/pii/S0095895684710732 para obter o melhor limite atual). Portanto, se você tiver uma estrutura tal que muitas cópias de possam ser empacotadas em$f \colon \mathbb{N} \to \mathbb{N}$$f(r)$$r \times r$$f$$S$$S$$r \times r$grade menor, então você sabe que qualquer gráfico de grande treewidth contém uma grande embalagem de cópias de . Por exemplo, como uma grade (para uniforme ) contém ciclos separados por vértices, segue-se que um gráfico da largura da árvore contém pelo menos separados ciclos.$S$$r \times r$$r$$(r/2)^2$$f(r)$$(r/2)^2$

O problema do conjunto independente máximo é um problema de empacotamento (você pode pensar em empacotar estrelas disjuntas) e possui um algoritmo conhecido com tempo de execução em gráficos com largura de árvore no máximo .$2^k \operatorname{poly(n)}$$k$

Uma referência maravilhosa sobre esse tópico é o artigo da pesquisa de Bruce Reed abaixo.

Reed, B. (1997). Largura e emaranhados das árvores: uma nova medida de conectividade e algumas aplicações. Pesquisas em combinatória, 241, 87-162.

Um dos meus trabalhos recentes permite ignorar o teorema da grade menor em alguns casos, via teoremas de decomposição de largura de árvore. Veja o artigo abaixo.

Decomposições e aplicações de gráficos com grande largura de árvore http://arxiv.org/abs/1304.1577

Essa também é uma resposta vaga. Existe uma dualidade semelhante ao teorema de Erdos-Posa para gráficos de largura de árvore limitada. Veja, por exemplo, Fedor V. Fomin, Saket Saurabh, Dimitrios M. Thilikos: Fortalecendo a propriedade Erdös-Pósa para classes de gráfico menores fechadas. Jornal da teoria dos grafos 66 (3): 235-240 (2011)