Existe-t-il un moyen de calculer la taille d'une correspondance maximale dans un graphe biparti non pondéré plus efficacement (par exemple, plus rapidement) que de calculer une correspondance maximale?
C'est un plan à long terme, mais c'est souvent un problème intéressant pour éviter des calculs jetables comme ceux-ci.
Motivation
Le problème que j'essaie de résoudre est le match-2 où les deux ensembles sont de tailles différentes. J'ai besoin de déterminer s'il existe une correspondance qui couvre tous les sommets du plus petit ensemble. Connaître la taille de la correspondance maximale me permettrait de vérifier si elle est égale ou inférieure à la taille de l'ensemble plus petit (si une telle chose est possible, chaque fois que le résultat est "oui, il existe une correspondance qui couvre le petit ensemble "vous sauriez effectivement quelle est sa taille mais seulement dans ce cas), mais ce n'est pas strictement nécessaire: s'il existe un moyen de calculer la réponse sans calculer la taille, c'est bon pour moi.