Contando el número de cubiertas de vértices: ¿cuándo es difícil?

Considere el problema # P-completo de contar el número de cubiertas de vértices de un gráfico dado $G = (V, E)$ .

Me gustaría saber si hay algún resultado que muestre cómo la dureza de dicho problema varía con algún parámetro de (por ejemplo, ).$G$$d = \frac{|E|}{|V|}$

Mi sensación es que el problema debería ser más fácil tanto cuando es escaso como cuando es denso, mientras que debería ser difícil cuando está "en el medio". ¿Es este realmente el caso?$G$$G$$G$

El problema de #VC de calcular el número de cubiertas de vértices de un gráfico dado sigue siendo # P-difícil para gráficos de 3 regulares; ver por ejemplo [Greenhill, 2000].

Para demostrar que el problema sigue siendo #VC # P-duro para gráficos con un máximo de $c\cdot n$ bordes, donde $n$ es el número de vértices y $0<c<3/2$ , reducir de la caja 3 regular mediante la adición de una lo suficientemente grande conjunto independiente (de tamaño lineal). El número de cubiertas de vértices sigue siendo el mismo si agrega un conjunto independiente.

Del mismo modo, para mostrar que el problema sigue siendo #VC # P-duro para gráficos con al menos $c\cdot n^2$ bordes, donde $n$ es el número de vértices y $0<c<1/2$ , a reducir de #VC mediante la adición de una lo suficientemente grande componente de camarilla (de tamaño lineal). El número de cubiertas de vértices se multiplica por $p+1$ si agrega una camarilla de tamaño $p$ a un gráfico.

Catherine S. Greenhill: La complejidad de contar colores y conjuntos independientes en gráficos e hipergrafías dispersos . Complejidad computacional 9 (1): 52-72 (2000)

Siguiendo la respuesta de Yaroslav, Luby y Vigoda fueron los primeros en mostrar un FPRAS para #IS bajo una condición de densidad (grado máximo 4, que supongo es más débil que el resultado de Weitz), mientras que Dyer, Frieze y Jerrum mostraron que no hay FPRAS para #IS si el grado máximo del gráfico es 25 a menos que RP = NP.

Referencias

Martin Dyer, Alan Frieze y Mark Jerrum. Al contar conjuntos independientes en gráficos dispersos. FOCS 1999.

Michael Luby y Eric Vigoda. Aproximadamente contando hasta cuatro. STOC 1997.

Véanse también las notas de la conferencia ETH de Jerrum, "Conteo, muestreo e integración: algoritmos y complejidad".

Con respecto a la complejidad de tiempo exponencial, los casos generales y casos con grado máximo constante son igualmente duro: El lema sparsification de Impagliazzo, Camas, Zane (2002) muestra que casos -Variable de d -Sat puede reducirse a instancias de d -Sat con a lo sumo f ( d , ϵ ) ⋅ n cláusulas en el tiempo exp ( ϵ n ) . Como se observó en el trabajo conjunto con Husfeldt y Wahlén, el lema de dispersión también funciona para las versiones de conteo de d -Sat, y especialmente para el caso de contar $n$$d$$d$$f(d,\epsilon)\cdot n$$\exp(\epsilon n)$$d$$2$-Sat (que es equivalente a contar conjuntos independientes y contar cubiertas de vértices).

$n$$\exp(o(n))$

Conjunto es una cubierta de vértice si su complemento es un conjunto independiente, por lo tanto, este problema es equivalente a contar conjuntos independientes.

El conteo algebraico de conjuntos independientes es FPT para gráficos de ancho de camarilla acotado acotado. Por ejemplo, vea "Un polinomio entrelazado multivariado de Courcelle y su cálculo para gráficos de ancho de camarilla acotado", donde calculan una generalización del polinomio de independencia. Sumar coeficientes de polinomio de independencia da el número de conjuntos independientes.

Los gráficos con un grado máximo 3 pueden tener un ancho de camarilla ilimitado.

El recuento numérico de conjuntos independientes es manejable cuando el problema exhibe "decadencia de correlación". Dror Weitz ( STOC'06 ) proporciona un FPTAS determinista para contar conjuntos independientes ponderados en gráficos de grado máximo$d$ cuando el peso $\lambda$ es

_{(source: yaroslavvb.com)}

Regular (unweighted) independent set counting corresponds to $\lambda=1$ so his algorithm gives FPTAS for number of vertex covers on graphs of maximum degree 5.

His algorithm is based on building a self-avoiding walk tree at each vertex, and truncating this tree at depth $d$. Branching factor of self-avoiding walk trees determines the range of $\lambda$ for which small depth $d$ gives a good approximation, and formula above is derived by using maximum degree of the graph to upper bound this branching factor.