Esto se suele denominar coincidencia perfecta y exacta problema. Se planteó en el documento La complejidad de los problemas de árboles de expansión restringidos de Papadimitriou y Yannakakis, y el documento Emparejar es tan fácil como la inversión de la matriz de Mulmuley, Vazirani y Vazirani da un algoritmo aleatorio de tiempo polinomial. No parece que se conozca un algoritmo determinista de tiempo polinómico. Deberías leer el artículo para obtener todos los detalles, pero lo resumiré.
La idea se basa en la Tutte matrix de $G$ . Esta matriz está definida por $$A_{ij} = \begin{cases} x_{ij} & \mbox{if}\;(i,j) \in E \mbox{ and } i<j\\ -x_{ji} & \mbox{if}\;(i,j) \in E \mbox{ and } i>j\\ 0 & \mbox{otherwise} \end{cases}$$ El determinante de $A$ es un polinomio en $|E(G)|$ variables; porque $A$ es simétrica, es el cuadrado de la Pfaffian de $A$ . Cada término en el Pfaffian corresponde a una correspondencia perfecta en $G$ En concreto, para una coincidencia $M$ obtenemos un término $\pm \prod_{e \in M} x_e$ .
Encontrar el determinante de la matriz de Tutte en términos de todas las $|E(G)|$ variables es difícil, pero sustituyendo los valores de cada $x_e$ y evaluar el determinante numéricamente es fácil. Esto da un algoritmo aleatorio para ver si $G$ tiene una correspondencia perfecta: introduzca valores aleatorios para cada $x_e$ y ver si el determinante es $0$ .
(La elección cuidadosa de las formas de introducir los valores aleatorios ofrece garantías de que esto funcionará bien; no es infalible porque las coincidencias múltiples podrían cancelarse para darnos un determinante de $0$ .)
Para el problema de coincidencia perfecta exacta, modificamos la matriz de Tutte: para cada arista roja $ij$ multiplicamos $x_{ij}$ por $y$ . Ahora, una coincidencia $M$ con $r$ los bordes rojos corresponden a un término $\pm y^r \prod_{e \in M}x_e$ en el Pfaffian, y para resolver el problema, debemos determinar si el coeficiente de $y^r$ en el Pfaffian es distinto de cero.
Si introducimos valores aleatorios para el $x_e$ esto da un polinomio en $y$ . No podemos encontrar este polinomio mediante un cálculo directo del determinante, pero con una sola variable involucrada, podemos hacerlo casi igual. Elige valores aleatorios para $x_e$ y probarlos con $n+1$ diferentes valores de $y$ . Esto evalúa el grado $n$ polinomio en $n+1$ puntos, y podemos interpolar para encontrar el polinomio - y ver cuál es el coeficiente de $y^r$ es.
De nuevo, obtener un coeficiente de $0$ no garantiza que no haya una coincidencia exacta: es posible que hayamos introducido el $x$ -valores y varios emparejamientos cancelados. Pero un lema de Mulmuley, Vazirani y Vazirani nos da una forma de garantizar que cuando hay una coincidencia exacta, obtenemos un coeficiente no nulo con alguna probabilidad razonable (suponiendo que los valores aleatorios se eligen correctamente). Si se repite el número suficiente de veces, podemos estar seguros de la respuesta.
