Compter et trouver toutes les correspondances parfaites / maximales dans les graphiques généraux

Récemment, j'ai été confronté à un problème qui m'a conduit aux questions suivantes:

• Existe-t-il un bon algorithme pour énumérer toutes les correspondances maximales / parfaites dans un graphique général?
• Existe-t-il un bon algorithme pour trouver toutes les correspondances maximales / parfaites dans un graphique général?
• Ces deux problèmes sont-ils équivalents dans leur complexité?

Je suis tombé sur les références suivantes:

• Algorithmes pour énumérer toutes les correspondances maximales et maximales parfaites dans les graphiques bipartites - Suggestion d'un algorithme pour énumérer toutes les correspondances maximales dans un graphique bipartite.
• Recherche de toutes les correspondances parfaites dans les graphiques bipartites - Suggestion d'un algorithme pour trouver toutes les correspondances parfaites dans les graphiques bipartites

La complexité des deux algorithmes dépend du nombre de correspondances parfaites dans le graphique (ce qui signifie le temps d'exécution exponentiel dans le pire des cas).

De plus, les deux articles traitent de graphes bipartis, je n'ai pas trouvé d'articles similaires traitant du même problème dans les graphes généraux.

J'apprécierais des informations et des références sur les problèmes ci-dessus.

Compter le nombre de correspondances parfaites dans les graphes bipartis équivaut à calculer la permanente de 0 à 1 matrices, ce qui est $\# P$-Achevée. Il s'ensuit qu'il y a une réduction de tous les autres problèmes de comptage que vous mentionnez (qui sont$\# P$) à ce problème. Vous pouvez calculer le nombre de correspondances parfaites dans les graphiques bipartites planaires et vous pouvez approximer le nombre de correspondances parfaites dans les graphiques bipartites généraux. Voir par exemple cette enquête . Il est apparemment plus difficile d'estimer le nombre de correspondances parfaites dans les graphiques généraux, voir par exemple ce papier ou ce papier . Les deux articles mentionnent que leurs algorithmes semblent bien fonctionner sur des graphiques aléatoires, mais pas nécessairement aussi bien dans le pire des cas.

Les problèmes de comptage et d'énumération des correspondances dans les graphiques sont de différents types, il est donc difficile de dire s'ils sont "équivalents". Notez cependant que si vous pouviez énumérer les correspondances, vous pourriez les compter. Cela montre que, dans un certain sens, il est plus difficile d'énumérer que de compter. Dans le cas des correspondances parfaites dans les graphiques bipartites, il semble y avoir une différence, car vous pouvez approximer le nombre de correspondances parfaites, mais les calculer exactement est$\# P$-difficile.