contando conjuntos independentes

8

Quais algoritmos / técnicas matemáticas estão disponíveis para contar exatamente / aproximadamente o número de conjuntos independentes?

Existe / há uma boa referência / boas referências sobre este tópico?

Estou interessado em gráficos regulares.

ds.algorithms reference-request graph-theory approximation-algorithms counting-complexity vs
fonte

1

A pesquisa no Google "contando gráficos regulares de conjuntos independentes" rende este artigo recente como terceiro resultado, o que fornece um limite superior.

Anthony Labarre

7

O problema pode ser corrigido como um # 2SAT. Vejo

http://en.wikipedia.org/wiki/2-satisfiability

na seção "Contando o número de atribuições satisfatórias" para algumas referências aos melhores algoritmos de contagem exata atualmente.

Andreas Björklund
fonte

Não vejo a conexão direta com conjuntos independentes nessa seção, embora em uma seção posterior eles tenham uma referência a gráficos bisplit (gráficos que podem ser divididos em um conjunto independente e um gráfico completo). Eu não acho que estou procurando por isso !! Estou perdendo uma conexão?

vs

5

G = (V, E)

$G = (V, E)$

u \in V

$u \in V$

x_{u}

$x_u$

(u, v) \in E

$(u, v) \in E$

\neg x_{u} \lor \neg x_{v}

$\neg x_u \vee \neg x_v$

Existe uma técnica semelhante para colorir?

vs

@vs Sim, a mesma construção com um tamanho de domínio maior.

Tyson Williams

5

Para uma contagem aproximada, o seguinte documento (também em APPROX-RANDOM 2011)

http://arxiv.org/abs/1105.5131

descreve o estado da arte.

$n$ $d$ $d$

Essa área de pesquisa baseia-se em muitos métodos matemáticos e algorítmicos e é uma área de interesse não apenas para cientistas teóricos da computação, mas também para teóricos dos números, probabilistas, combinatorialistas, físicos estatísticos e muito mais. Esses dois artigos recentes podem dar um bom começo, embora exista uma rica coleção de artigos profundos e interessantes sobre o assunto, que remontam a décadas.

RJK
fonte

4

Para complementar a resposta do @RJK, a partir de ontem, existe um novo "estado da arte".

Manhoso e sol mostram

$d \ge 3$ $\lambda > \lambda_c(d) = \frac{(d−1)^{d-1}}{(d-2)^d}$ $\lambda$ $d$

$\lambda < \lambda_c(d)$

$\lambda = \lambda_c(d)$

Tyson Williams
fonte

Você sabe se esses resultados são válidos para gráficos com estrutura específica, como produtos fortes e fracos (etc), cujo gráfico subjacente tem menos de 3 e qual tem o valor de lambda menor que o acima?

vs

@v Estes gráficos são regulares?

Tyson Williams

Sim. Mas os resultados implicam em todos os gráficos regulares, sem ressalvas? (Estou pensando em algo análogo a isso - sabemos que é NP difícil decodificar ML um código linear .. mas é muito difícil mostrar códigos não triviais específicos, como códigos RS, e também é conhecido que existem códigos onde decodificação ML é fácil) Obviamente, parece que o resultado aqui é válido para todos os gráficos regulares. mas há casos em que a simetria do gráfico também pode ajudar e não vejo que esses gráficos (no artigo) tenham alguma simetria em absoluto!!

vs

1

@v Este resultado é válido para todos os

d

d

$d$ gráficos -regulares. Não sei muito sobre a teoria da codificação. Talvez você deva fazer uma nova pergunta.

Tyson Williams

contando conjuntos independentes

Respostas: