Quando é relaxado a contagem difícil?

26

Suponha que relaxemos o problema de contar cores apropriadas contando as cores ponderadas da seguinte maneira: toda cor adequada ganha peso 1 e toda cor imprópria ganha peso onde c é uma constante e v é o número de arestas com pontos finais com a mesma cor. Quando c vai para 0, isso reduz a contagem de cores adequadas, o que é difícil para muitos gráficos. Quando c é 1, todos os corantes recebem o mesmo peso e o problema é trivial. Quando a matriz de adjacência do gráfico multiplicada por - log ( c ) / 2 tem raio espectral abaixo de 1 - ϵcvcvclog(c)/21ϵ, essa soma pode ser aproximada pela propagação de crenças com garantia de convergência, por isso é fácil na prática. Também é fácil em teoria porque uma árvore de computação específica exibe decaimento de correlações e, portanto, permite um algoritmo de tempo polinomial para aproximação garantida - Tetali, (2007)

Minha pergunta é: que outras propriedades do gráfico dificultam esse problema para algoritmos locais? Difícil, no sentido de que apenas um pequeno intervalo de 's pode ser tratado.c

23/09 : Até agora, deparei-me com dois algoritmos de aproximação polinomial determinística para essa classe de problemas (derivados do artigo STOC2006 de Weitz e da abordagem de "expansão de cavidades" de Gamarnik para aproximar a contagem), e ambas as abordagens dependem do fator de ramificação da auto- evitando caminhadas no gráfico. O raio espectral surge porque é um limite superior nesse fator de ramificação. A questão é então - é uma boa estimativa? Poderíamos ter uma sequência de gráficos em que o fator de ramificação das caminhadas por autoavaliação é limitado, enquanto o fator de ramificação das caminhadas regulares cresce sem limites?

Edit 10/06 : Este artigo de Allan Sly (FOCS 2010) parece relevante ... o resultado sugere que o fator de ramificação da árvore infinita de caminhadas que evitam a auto-captura capta com precisão o ponto em que a contagem se torna difícil.

Editar 10/31 : conjecturas de Alan Sokal ( p.42 de "A polinomia Tutiv multivariada" ) de que a existe um limite superior no raio da região livre de zero do polinômio cromático que é linear em termos de maxmaxflow (fluxo st máximo sobre todos os pares s, t). Isso parece relevante porque correlações de longo alcance aparecem quando o número de cores adequadas se aproxima de 0.

Yaroslav Bulatov
fonte
3
Ótima pergunta.
András Salamon
1
Isso será familiar para qualquer pessoa que trabalhe nesta área, mas talvez você possa mencionar que o problema exato para cores ec 1 é conhecido por ser # P-hard pelo Teorema 1 de "A complexidade das funções de partição" de A . Bulatov & Grohe, porque o k x k matriz com c na diagonal e um outro lugar tem posto, pelo menos, 2.k3c1k×kc1
Colin McQuillan
1
Além disso, este é o modelo de Potts do estado q antiferromagnético, correto?
Colin McQuillan
1
@ Kaveh: Você poderia reverter isso? Essas duas tags, embora menos populares, descreveram melhor essa pergunta. Marcar novamente todas as perguntas para incluir apenas as tags mais populares parece-me falso.
RJK
1
@Kaveh: Por que você não pergunta ao OP quais tags arXiv ele deseja e quais tags não arXiv ele deseja remover, em vez de fazer uma escolha unilateral de acordo com a popularidade? Não concordo com o argumento de que fornecer tags mais gerais organiza melhor o site. Minhas tags favoritas não incluem nenhuma de nível superior.
RJK

Respostas:

11

Isso é difícil para gráficos planares, pelo menos para seis cores ou mais. Veja "Inaproximabilidade do polinômio de Tutte de um gráfico planar" de Goldberg e Jerrum

Colin McQuillan
fonte
Observe que isso está perguntando sobre a versão descontraída da contagem. Para qualquer gráfico, há uma gama de cs para os quais é fácil contar descontraidamente. A questão é como quantificar esse intervalo
Yaroslav Bulatov 10/10
3
ESTÁ BEM. Parece que eu roubei a recompensa que você ofereceu, então vou oferecer 50 pontos nessa questão.
Colin McQuillan
bom gesto, Colin!
Suresh Venkat
Não havia outras respostas e os 50 pontos teriam sido perdidos de outra maneira! O sistema impõe um limite arbitrário de 7 dias para recompensas. Consulte meta.stackexchange.com/questions/1413/… para discussão das alterações mais recentes no sistema.
András Salamon
5

Mais alguns comentários:

Um algoritmo local para contagem calculará a contagem a partir de um conjunto de estatísticas por nó em que cada estatística é uma função de alguma vizinhança gráfica do nó. Para os corantes, essas estatísticas estão relacionadas à "probabilidade marginal de encontrar a cor c". Aqui está um exemplo dessa redução para um gráfico simples.

Segue-se do artigo recente de Alan Sly que contar conjuntos independentes usando um algoritmo local é tão difícil quanto contar conjuntos independentes usando qualquer algoritmo. Suspeito que isso seja verdade para a contagem geral de gráficos.

Para algoritmos locais, a dureza depende de como a correlação entre nós se comporta em relação à distância entre nós. Para distâncias suficientemente grandes, essa correlação tem basicamente apenas dois comportamentos - a correlação decai exponencialmente na distância do gráfico ou não decai.

Se houver decaimento exponencial, as estatísticas locais dependem de uma vizinhança cujo tamanho é polinomial no tamanho do gráfico, portanto, o problema da contagem é fácil.

Nos modelos de física estatística, observou-se (de Gennes, Emery) que há uma conexão entre caminhadas evitáveis, deterioração da correlação e transições de fase. O ponto em que a função geradora para caminhadas por auto-evitação em uma treliça se torna infinita corresponde à temperatura na qual as correlações de longo alcance aparecem no modelo.

Você pode ver na construção da árvore de caminhada que evita a evitação de Weitz por que as caminhadas evitáveis ​​surgem em decaimento de correlação - o marginal pode ser representado exatamente como a raiz de uma árvore de caminhadas evitáveis; pequenas o suficiente, as folhas da árvore tornam-se irrelevantes eventualmente.

Se a "dureza local" implica dureza, é suficiente quantificar propriedades que determinam a taxa de crescimento de caminhadas que evitam a auto-evitação. A taxa de crescimento exata pode ser extraída da função de geração para caminhadas que evitam a auto-evitação, mas é impossível calcular a quantidade. O raio espectral é fácil de calcular e fornece um limite inferior.

Yaroslav Bulatov
fonte
2
este é um bom resumo e obrigado pelo ponteiro do artigo de Allan Sly: agora estou inspirado a participar da palestra!
Suresh Venkat
4

Alguns comentários: não é uma resposta.

ccc[0,ϵ)ϵ>0cc ).

c

Você está solicitando propriedades estruturais da classe de gráficos que permitiriam que o problema permanecesse difícil. Até onde eu sei, será quase sempre difícil. Mas isso é muito superficial e precisa de mais trabalho.

András Salamon
fonte