contando conjuntos independientes

8

¿Qué algoritmos / técnicas matemáticas están disponibles para contar exactamente / aproximadamente el número de conjuntos independientes?

¿Hay / hay una buena referencia / buenas referencias sobre este tema?

Estoy interesado en gráficos regulares.

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

1

Buscar en Google "contar gráficos independientes de conjuntos regulares" arroja este artículo reciente como tercer resultado, lo que da un límite superior.

Anthony Labarre

7

El problema se puede restablecer como un # 2SAT. Ver

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

en la sección "Contar el número de asignaciones satisfactorias" para algunas referencias a los mejores algoritmos de conteo exactos en la actualidad.

Andreas Björklund
fuente

No veo la conexión directa a conjuntos independientes en esa sección, aunque en una sección posterior tienen una referencia a gráficos bisplit (gráficos que se pueden dividir en un conjunto independiente y gráfico completo). ¡No creo que esté buscando esto! ¿Me estoy perdiendo una conexión?

vs

55

@vs qué tal: para

, para cada

, tener variable

, y para cada

tener cláusula

. todas las variables establecidas en verdadero corresponden a un conjunto independiente.

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$

Sasho Nikolov

¿Existe una técnica similar para colorear?

vs

@vs Sí, la misma construcción con un tamaño de dominio más grande.

Tyson Williams

5

Para un recuento aproximado, el siguiente documento (también en APROX-RANDOM 2011)

http://arxiv.org/abs/1105.5131

describe el estado del arte.

Como Anthony Labarre se refiere en un comentario anterior, hubo un avance reciente e inesperado de Yufei Zhao que muestra un límite superior ajustado en el número de conjuntos independientes en un gráfico -vertex -regular. Su prueba utilizaba una biyección muy inteligente. El ejemplo extremo, conjeturado por Alon y Kahn y que data de 1991, es simplemente una unión disjunta de muchas copias de un gráfico bipartito completo regular. $n$ $d$ $d$

Esta área de investigación se basa en muchos métodos matemáticos y algorítmicos, y es un área de interés no solo para los científicos teóricos de la informática, sino también para los teóricos, probabilistas, combinatorios, físicos estadísticos y más. Estos dos documentos recientes pueden darle un buen comienzo, aunque hay una rica colección de documentos profundos e interesantes sobre el tema que se remontan a décadas.

RJK
fuente

4

Para complementar la respuesta de @RJK, a partir de ayer, hay un nuevo "estado del arte".

Espectáculo astuto y sol

$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
fuente

¿Sabe si estos resultados son válidos para gráficos con una estructura específica, como productos fuertes, débiles (etc.) cuyo gráfico subyacente es dergee menor que 3 y que tiene el valor de lambda menor que el anterior?

vs

@v ¿Estas gráficas son regulares?

Tyson Williams

Si. ¿Pero los resultados implican para todos los gráficos regulares, sin advertencia? (Estoy pensando en algo análogo a esto: sabemos que NP es difícil decodificar en ML un código lineal ... pero es muy difícil de mostrar para códigos específicos no triviales como los códigos RS y también se sabe que hay códigos donde la decodificación ML es fácil) Por supuesto, parece que el resultado aquí se cumple para todos los gráficos regulares ... pero hay casos en los que la simetría del gráfico también puede ayudar y no veo que se suponga que estos gráficos (en el documento) tengan alguna simetría ¡¡en absoluto!!

vs

1

d

$d$

contando conjuntos independientes

Respuestas: