Existence d'un appariement parfait biparti

Question

Soit $ B = G (L, R, E) $ est un graphe bipartite. Je veux savoir si ce graphique a une correspondance parfaite. Une façon de tester si ce graphique a une concordance parfaite est le mariage théorème de Hall, mais il est inefficace (i.e. $ | \ mathcal P (L) | = 2 ^ {| L |} tests $ - non polynomiale). Je peux toujours savoir si un appariement parfait existe en calculant une correspondance cardinalité maximum et de tester sa perfection, mais cela implique le calcul de ce couplage parfait.

Y at-il un efficace façon de décider si une correspondance parfaite biparti existe sans calculer l'appariement elle-même? Idéalement, je voudrais un algorithme qui est plus rapide que les algorithmes comme Hopcroft Karp ou algorithmes correspondants à base de matrice, qui trouvent explicitement la mise en correspondance (i.e. afin de ne pas calculer l'appariement est logique).

Edit:. La partie en italique

Answer 1

Une revue de la littérature rapide suggère que le plus rapide algorithme pour décider si un graphe biparti dense a une correspondance parfaite est toujours l'algorithme de matrice, qui se déroule dans le temps $ O (| V | ^ \ omega) $ . Vous pouvez réduire l'espace de l'algorithme, consultez isolement, d'alignement et de comptage par Allender, Reinhardt et Zhou. Un article récent à partir de 2010, qui met l'accent sur graphes planaires, suggère que le résultat de Allender et al. est le meilleur qui est connu.