Esistenza di abbinamento perfetto bipartita

Question

Sia $ B = G (L, R, E) $ un grafo bipartito. Voglio scoprire se questo grafico ha una corrispondenza perfetta. Un modo per verificare se questo grafico ha un abbinamento perfetto è di Hall Matrimonio Teorema, ma è inefficiente (cioè $ | \ P mathcal (L) | = 2 ^ {| L |} $ test - non polinomiale). Posso sempre scoprire se un accoppiamento perfetto esiste calcolando un accoppiamento massimo cardinalità e testare la sua perfezione, ma questo comporta il calcolo che perfetta corrispondenza.

C'è un efficace modo di decidere se esiste una corrispondenza perfetta bipartito senza calcolare l'abbinamento è di per sé? Idealmente vorrei un algoritmo che è più veloce di algoritmi come Hopcroft Karp o algoritmi di matching matrice base, che trovano esplicitamente l'abbinamento (cioè in modo non calcolando l'abbinamento ha un senso).

Modifica:. La parte in corsivo

Answer 1

Una revisione rapida letteratura suggerisce che l'algoritmo più veloce per decidere se un grafo bipartito densa ha una corrispondenza perfetta è ancora l'algoritmo di matrice, che viene eseguito in tempo $ O (| V | ^ \ omega) $ . È possibile ridurre lo spazio dell'algoritmo, vedi isolamento, Matching e Counting di Allender, Reinhardt e Zhou. Un recente di carta a partire dal 2010, che si concentra su grafi planari, suggerisce che il risultato di Allender et al. è la migliore che si conosca.