Compter le nombre de couvertures de sommets: quand est-ce difficile?

Considérons le problème # P-complet de compter le nombre de couvertures de sommets d'un graphe donné $G = (V, E)$ .

Je voudrais savoir s'il y a un résultat montrant comment la dureté d'un tel problème varie avec un paramètre de $G$ (par exemple, $d = \frac{|E|}{|V|}$).

Ma sensation est que le problème devrait être plus facile à la fois lorsque est clairsemé et lorsque est dense, alors qu'il devrait être difficile lorsque est "au milieu". Est-ce vraiment le cas?G $G$$G$$G$

Le problème #VC de calcul du nombre de couvertures de sommets d'un graphe donné reste # P-difficile pour les graphes à 3 régularités; voir par exemple [Greenhill, 2000].

Pour montrer que le problème reste #VC # P-dur pour les graphes avec au plus $c\cdot n$ arêtes, où $n$ est le nombre de sommets et $0<c<3/2$ , réduire le cas 3 régulier en ajoutant un assez grand ensemble indépendant (de taille linéaire). Le nombre de couvertures de sommets reste le même si vous ajoutez un ensemble indépendant.

De même, pour montrer que le problème reste #VC # P-dur pour les graphes avec au moins $c\cdot n^2$ bords, où $n$ est le nombre de sommets et $0<c<1/2$ , réduire de #VC en ajoutant un assez grand composante clique (de taille linéaire). Le nombre de couvertures de sommets est multiplié par $p+1$ si vous ajoutez une clique de taille $p$ à un graphique.

Catherine S. Greenhill: La complexité du comptage des colorations et des ensembles indépendants dans les graphiques clairsemés et les hypergraphes . Complexité informatique 9 (1): 52-72 (2000)

Suite à la réponse de Yaroslav, Luby et Vigoda ont été les premiers à montrer un FPRAS pour #IS dans une condition de densité (degré maximum 4, qui je suppose est plus faible que le résultat de Weitz), tandis que Dyer, Frieze et Jerrum ont montré qu'il n'y avait pas de FPRAS pour #IS si le degré maximum du graphique est de 25 sauf si RP = NP.

Les références:

Martin Dyer, Alan Frieze et Mark Jerrum. Sur le comptage d'ensembles indépendants dans des graphes clairsemés. FOCS 1999.

Michael Luby et Eric Vigoda. Compter environ jusqu'à quatre. STOC 1997.

Voir aussi les notes de cours ETH de Jerrum, "Comptage, échantillonnage et intégration: algorithmes et complexité".

En ce qui concerne la complexité temporelle exponentielle, les instances générales et les instances à degré maximum constant sont également difficiles: le lemme de sparsification d' Impagliazzo, Paturi, Zane (2002) montre que instances variables de d -Sat peuvent être réduites à des instances de$n$$d$ -Sat avec au plus f ( d , ϵ ) ⋅ n clauses dans le temps exp ( ϵ n ) . Comme observé dansle travail conjointavec Husfeldt et Wahlén, le lemme de sparsification fonctionne également pour les versions de comptage de d -Sat, et en particulier pour le cas de comptage$d$$f(d,\epsilon)\cdot n$$\exp(\epsilon n)$$d$$2$-Sat (ce qui équivaut à compter des ensembles indépendants et à compter les couvertures de sommets).

De plus, le comptage d'ensembles indépendants dans un graphe -vertex ne peut pas être fait en temps exp ( o ( n ) ) à moins que l' hypothèse de temps exponentielle échoue. Il s'agit d'une observation encore inédite annoncée lors d' une conférence lors du Dutstuhl Seminar Computational Counting .$n$$\exp(o(n))$

L'ensemble est une couverture de sommets si son complément est un ensemble indépendant, donc ce problème équivaut à compter des ensembles indépendants.

Le comptage algébrique des ensembles indépendants est FPT pour les graphiques de largeur de clique bornée bornée. Par exemple, voir «Un polynôme entrelacé multivarié et son calcul pour les graphiques de largeur de clique bornée» de Courcelle, où ils calculent une généralisation du polynôme d'indépendance. La somme des coefficients du polynôme d'indépendance donne le nombre d'ensembles indépendants.

Les graphiques avec un degré maximum 3 peuvent avoir une largeur de clique illimitée.

$d$$\lambda$

_{(source: yaroslavvb.com )}

$\lambda=1$

$d$$\lambda$$d$