Largura e embalagem das árvores

9

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.

Nikhil
fonte

Respostas:

11

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/bxm037kkpara 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 emf:NNf(r)r×rfSSr×rgrade 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.Sr×rr(r/2)2f(r)(r/2)2

Bart Jansen
fonte
Bart: Talvez isso seja irrelevante, mas você vê alguma relação entre a reconstrução do gráfico e a largura da árvore? Você também tem um link para a versão gratuita do seu artigo? (Otimização combinatória em gráficos de largura de árvore limitada)
Saeed
O papel treewidth está disponível em CiteSeer citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.2561 . Quanto à reconstrução do gráfico: você quer dizer o processo em que, considerando o multiset de todos os subgráficos obtidos pela exclusão de um único vértice, deseja reconstruir o gráfico original? Parece que Shiva Kintali examinou recentemente a questão de saber se a conjectura de reconstrução gráfica é verdadeira para a segunda largura: cstheory.stackexchange.com/questions/5155/… .
Bart Jansen
Obrigado Bart, sim, eu vejo a pergunta de Shiva, mas, foi por um ano atrás, pode haver algum resultado novo, obrigado em tudo.
Saeed
O site de Shiva lista dois manuscritos sobre o assunto, "Sobre a reconstrução de árvores-k e árvores de gráficos regulares" e "Novas propriedades de gráficos reconstrutíveis" com uma nota "PDF em breve" ( cs.princeton.edu/~kintali/#proprecon ) Você pode entrar em contato diretamente com ele para perguntar sobre o estado da arte atual.
Bart Jansen
Posteriormente a essa resposta, Kawarabayashi e Kobayashi melhoraram a largura da árvore necessária para garantir uma grade menor para em dx.doi.org/10.4230/ LIPIcs.STACS.2012.278 e Seymour reivindicaram uma melhoria para em agosto de 2012.r×r2O(r2logr)2O(rlogr)
András Salamon
7

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 . k2kpoly(n)k

Janne H. Korhonen
fonte
Janne, obrigado pela sua resposta. Estou ciente do algoritmo MIS. Além do MIS, a noção de largura das árvores foi aplicada ao empacotamento de outras estruturas? Além disso, não estou inteiramente convencido de pensar em MIS como uma embalagem de estrelas disjuntas, você poderia, por favor, explicar seu ponto de vista sobre isso? (qual estrutura estelar você está tentando agrupar, qual é a noção de "estrelas disjuntas")?
21412 Nikhil
11
Não é tão simples como eu pensava ao postar a resposta. "Empacotar estrelas disjuntas pela borda" seria mais apropriado e, então, você precisará exigir que qualquer estrela colocada tenha o maior grau possível. Não me lembro de ver a largura da árvore aplicada a problemas de embalagem mais complexos.
Janne H. Korhonen
11
O conjunto independente máximo é certamente um "problema de empacotamento" na terminologia usual; outro exemplo de problema de empacotamento é a correspondência máxima. (Eles estão fazendo as malas programas inteiros; o relaxamento LP é um LP de embalagem.)
Jukka Suomela
6

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

Chandra Chekuri
fonte
5

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)

R2-D2
fonte