Existenz von zweiparteilen perfekter Matching

Question

Sei $ b = g (l, r, e) $ ein zweipartneres Diagramm. Ich möchte herausfinden, ob diese Grafik eine perfekte Übereinstimmung hat. Eine Möglichkeit zu testen, ob dieses Diagramm eine perfekte Übereinstimmung hat, ist Halls Ehe -Theorem, aber es ist ineffizient (dh $ | mathcal p (l) | = 2^{| l |} $ Tests - nicht Polynom). Ich kann immer herausfinden, ob eine perfekte Übereinstimmung vorhanden ist, indem ich eine maximale Kardinalitätsübereinstimmung und das Testen ihrer Vollkommenheit berechnet, aber dies beinhaltet die Berechnung dieser perfekten Übereinstimmung.

Ist dort ein effizient Weg zu entscheiden, ob ein perfektes zweipartneres Matching existiert, ohne dass das Selbst selbst berechnet wird? Idealerweise möchte ich einen Algorithmus, der schneller als Algorithmen wie Hopcroft Karp oder Matrixbasis -Matching -Algorithmen ist, die explizit die Übereinstimmung herausfinden (dh das Nichtberechnen der Übereinstimmung ist sinnvoll).

Bearbeiten: Der kursive Teil.

Answer 1

Eine schnelle Literaturübersicht legt nahe, dass der schnellste Algorithmus zur Entscheidung, ob ein dichter zweigliedriger Diagramm eine perfekte Übereinstimmung hat, immer noch der Matrixalgorithmus ist, der rechtzeitig läuft $ O (| v |^ Omega) $. Sie können den Raum des Algorithmus reduzieren, siehe Isolation, Übereinstimmung und Zählen von Allender, Reinhardt und Zhou. Eine kürzlich durchgeführte Arbeit Ab 2010, das sich auf planare Graphen konzentriert, legt das Ergebnis von Allender et al. ist das Beste, was bekannt ist.