Quelle est la difficulté de compter le nombre de chemins simples entre deux nœuds dans un graphe orienté?

Il existe un algorithme polynomial facile pour décider s'il existe un chemin entre deux nœuds dans un graphe orienté (il suffit de faire un parcours de graphe de routine avec, disons, la profondeur en premier).

Cependant, il semble que, de manière surprenante, le problème devienne beaucoup plus difficile si, au lieu de tester l'existence, nous voulons compter le nombre de chemins.

Si nous permettons aux chemins de réutiliser les sommets, il existe une solution de programmation dynamique pour trouver le nombre de chemins de s à t avec n arêtes. Cependant, si nous n'autorisons que des chemins simples, qui ne réutilisent pas les sommets, la seule solution à laquelle je peux penser est l'énumération par force brute des chemins , quelque chose qui a une complexité temporelle exponentielle.

Alors je demande,

• Est-ce difficile de compter le nombre de chemins simples entre deux sommets?
• Si oui, est-ce que c'est NP-complet? (Je dis en quelque sorte parce que ce n'est techniquement pas un problème de décision ...)
• Y a-t-il d'autres problèmes dans P qui ont aussi des versions de comptage comme ça? **

La classe de complexité la plus courante associée aux problèmes de comptage est #P . Décider s'il existe un chemin simple d'un nœud donné à un autre est clairement dans NP. Les compter est alors en #P.

A propos de l'exhaustivité de NP: même si ce n'est pas un problème de décision, cela ne rentrerait guère dans NP: il peut y avoirchemins, et le non-déterminisme ne vous aide pas à ce sujet (vous auriez encore besoin de les vérifier tous)$n!$

La réponse à vos deux premières questions est: oui, c'est difficile, c'est # P-complete (ref) .

L' article de Wikipédia donne des faits pertinents: 1) les algorithmes probabilistes sont utiles pour approximer les fonctions # P-complètes, et c'est le type d'algorithme utilisé pour l'approximation dans l'article précédent. 2) Il existe d'autres problèmes faciles avec les versions de comptage dur (# P-complet):

• trouver (linéaire) vs compter toutes les affectations satisfaisant une formule DNF ou une instance de 2-SAT
• trouver (linéaire) vs compter les tri topologiques
• trouver (O (VE)) vs compter la correspondance parfaite dans les graphiques bipartites

Vous savez déjà que si vous supprimez la contrainte "chemin simple" le problème tombe en P (enfin vous devez délimiter la longueur des chemins par un polynôme de la taille du graphe ou donner la limite en unaire)