Contando o número de capas de vértices: quando é difícil?

Considere o problema # P-complete de contar o número de coberturas de vértices de um determinado gráfico .$G = (V, E)$

Gostaria de saber se há algum resultado mostrando como a dureza desse problema varia com algum parâmetro de (por exemplo, d = | E $G$)$d = \frac{|E|}{|V|}$

Minha sensação é que o problema deve ser mais fácil quando é escasso e quando G é denso, enquanto que deve ser difícil quando G está "no meio". É este realmente o caso?$G$$G$$G$

O problema #VC de calcular o número de capas de vértices de um determinado gráfico permanece # P-difícil para gráficos tridimensionais; veja por exemplo [Greenhill, 2000].

Para mostrar que o problema permanece #VC # P-duro para gráficos com, no máximo, $c\cdot n$ bordas, onde $n$ é o número de vértices e $0<c<3/2$ , a partir de reduzir o caso 3-regular, através da adição de um grande o suficiente conjunto independente (de tamanho linear). O número de capas de vértice permanece o mesmo se você adicionar um conjunto independente.

Da mesma forma, para mostrar que o problema permanece #VC # P-duro para gráficos com, pelo menos, $c\cdot n^2$ bordas, onde $n$ é o número de vértices e $0<c<1/2$ , a partir de reduzir #VC pela adição de um grande o suficiente componente de clique (de tamanho linear). O número de capas de vértices é multiplicado por $p+1$ se você adicionar um clique do tamanho $p$ a um gráfico.

Catherine S. Greenhill: A complexidade da contagem de cores e conjuntos independentes em gráficos esparsos e hipergrafos . Complexidade Computacional 9 (1): 52-72 (2000)

Seguindo a resposta de Yaroslav, Luby e Vigoda foram os primeiros a mostrar um FPRAS para #IS sob uma condição de densidade (grau máximo 4, que suponho que seja mais fraco que o resultado de Weitz), enquanto Dyer, Frieze e Jerrum mostraram que não há FPRAS para #IS se o grau máximo do gráfico for 25, a menos que RP = NP.

Referências:

Martin Dyer, Alan Frieze e Mark Jerrum. Contando conjuntos independentes em gráficos esparsos. FOCS 1999.

Michael Luby e Eric Vigoda. Contando aproximadamente até quatro. STOC 1997.

Veja também as notas da aula ETH de Jerrum, "Contando, amostrando e integrando: algoritmos e complexidade".

Com relação à complexidade de tempo exponencial, instâncias gerais e instâncias com grau máximo constante são igualmente difíceis: O lema de esparsificação de Impagliazzo, Paturi, Zane (2002) mostra que instâncias variáveis ​​de d -Sat podem ser reduzidas a instâncias de d -Sat com no máximo f ( d , ϵ ) ⋅ n cláusulas no tempo exp ( ϵ n ) . Como observado no trabalho conjunto com Husfeldt e Wahlén, o lema da esparsificação também funciona para as versões contadoras do d -Sat, e especialmente para o caso da contagem $n$$d$$d$$f(d,\epsilon)\cdot n$$\exp(\epsilon n)$$d$$2$-Sat (que é equivalente a contar conjuntos independentes e contar capas de vértices).

Além disso, a contagem de conjuntos independentes em um gráfico vertex não pode ser feita no tempo exp ( o ( n ) ) , a menos que a hipótese do tempo exponencial falhe. Esta é uma observação ainda não publicada anunciada em uma palestra durante a contagem computacional do seminário de Dagstuhl .$n$$\exp(o(n))$

Conjunto é uma cobertura de vértice se seu complemento é um conjunto independente, portanto, esse problema é equivalente a contar conjuntos independentes.

A contagem algébrica de conjuntos independentes é FPT para gráficos de largura de clique limitada limitada. Por exemplo, consulte "Um polinômio multivariado de entrelaçamento e sua computação para gráficos de largura de clique limitada", onde eles calculam uma generalização do polinômio de independência. A soma dos coeficientes do polinômio de independência fornece o número de conjuntos independentes.

Os gráficos com grau máximo 3 podem ter largura de clique ilimitada.

$d$$\lambda$

_{(fonte: yaroslavvb.com )}

$\lambda=1$

$d$$\lambda$$d$