Contar y encontrar todas las coincidencias perfectas / máximas en gráficos generales

Recientemente he estado lidiando con un problema que me llevó a las siguientes preguntas:

• ¿Existe un buen algoritmo para enumerar todas las coincidencias máximas / perfectas en un gráfico general?
• ¿Existe un buen algoritmo para encontrar todas las coincidencias máximas / perfectas en un gráfico general?
• ¿Son estos dos problemas equivalentes en su complejidad?

Me he topado con las siguientes referencias:

• Algoritmos para enumerar todas las coincidencias máximas y máximas perfectas en gráficos bipartitos : se sugiere un algoritmo para enumerar todas las coincidencias máximas en un gráfico bipartito.
• Encontrar todas las coincidencias perfectas en gráficos bipartitos : se sugiere un algoritmo para encontrar todas las coincidencias perfectas en gráficos bipartitos

La complejidad de ambos algoritmos depende del número de coincidencias perfectas en el gráfico (lo que significa tiempo de ejecución exponencial en el peor de los casos).

Además, ambos artículos tratan con gráficos bipartitos, no pude encontrar artículos similares que aborden el mismo problema en los gráficos generales.

Agradecería información y referencias sobre los problemas anteriores.

Contar el número de coincidencias perfectas en gráficos bipartitos equivale a calcular el permanente de 0-1 matrices, que es $\# P$-completar. Se deduce que hay una reducción de todos los otros problemas de conteo que usted menciona (que están todos en$\# P$) a este problema. Puede calcular el número de coincidencias perfectas en gráficos bipartitos planos , y puede aproximar el número de coincidencias perfectas en gráficos bipartitos generales. Ver por ejemplo esta encuesta . Aproximadamente el número de coincidencias perfectas en gráficos generales es aparentemente más difícil, ver por ejemplo este documento o ese documento . Ambos documentos mencionan que sus algoritmos parecen funcionar bien en gráficos aleatorios, pero no necesariamente tan bien en el peor de los casos.

Los problemas de contar y enumerar coincidencias en gráficos son de diferentes tipos, por lo que es difícil decir si son "equivalentes". Sin embargo, tenga en cuenta que si pudiera enumerar coincidencias, podría contarlas. Esto muestra que, en cierto sentido, enumerar es más difícil que contar. Para el caso de coincidencias perfectas en gráficos bipartitos, parece haber una diferencia, ya que puede aproximar el número de coincidencias perfectas, pero calcularlas exactamente es$\# P$-difícil.