Complexité du comptage de tous les sous-graphiques connectés

Soit G un graphe connecté.

Quelle est la complexité du comptage de tous les sous - graphiques connectés si G est des types suivants?

• G est général.
• G est plan.
• G est bipartite.

Je ne me soucie pas des structures ou ..., il suffit de compter tous les sous-graphiques connectés! Je suis également intéressé par la complexité de compter tous les sous-graphes connectés avec exactement k nœuds en G.

Les pointeurs vers des articles et des livres sont également les bienvenus!

Welsh déclare que le problème # P-complet même dans le cas le plus restreint (en comptant le nombre de sous-graphes connectés d'un graphe biparti plan). Voir le bas de la page 305 dans Welsh, Dominic (1997), "Approximate Counting", Surveys in Combinatorics , Bailey, RA, éd., Cambridge University Press, pp. 287–324.

Dans le contexte, cependant, je me demande s'il veut vraiment dire des sous-graphiques étendus connectés. Et cela m'amène à me demander quelle version du problème vous voulez: des sous-graphiques étendus connectés, des sous-graphiques connectés qui n'ont pas besoin d'être étendus, ou des sous-graphiques induits connectés?

Ceci est une réponse à la réponse de David. Sans avoir encore regardé ce livre, je suppose que le problème est de compter les sous-graphiques étendus connectés, car il s'agit du point x = 1 y = 2 du polynôme de Tutte, et l'auteur était intéressé par cela. Mais en fait, je pense que ces trois problèmes se réduisent assez facilement à compter le problème de sous-graphe couvrant connecté. Les réductions suivantes devraient fonctionner pour le comptage exact ou l'approximation, bien que je pense que le problème d'approximation est toujours ouvert.

$K_A$$A$

$K_A$$A$

$\#P$