¿Existe una reducción directa / natural para contar los emparejamientos perfectos no bipartitos usando el permanente?

Contar el número de coincidencias perfectas en un gráfico bipartito se puede reducir de inmediato a calcular el permanente. Dado que encontrar una coincidencia perfecta en un gráfico no bipartito está en NP, existe una reducción de los gráficos no bipartitos al permanente, pero puede implicar una explosión polinómica desagradable al usar la reducción de Cook a SAT y luego el teorema de Valiant para reducir al permanente.

Una reducción eficiente y natural de un gráfico no bipartito a una matriz donde sería útil para una implementación real para contar coincidencias perfectas mediante el uso existente, altamente optimizado bibliotecas que computan lo permanente. $f$ $G$ $A = f(G)$ $\operatorname{perm}(A) = \Phi(G)$

Actualizado: agregué una recompensa por una respuesta que incluye una función computable eficientemente para llevar un gráfico arbitrario a un gráfico bipartito con el mismo número de coincidencias perfectas y no más de vértices . $G$ $H$ $O(n^2)$

graph-theory counting-complexity reductions permanent Derrick Stolee
fuente

El título actual suena como una pregunta de tarea, pero la pregunta real es mucho más interesante que eso. Casi ni siquiera abrí la pregunta porque creía que era tarea y pronto se cerraría, hasta que vi que ya tenía 9 votos a favor y tuve curiosidad ... Tal vez cambie el título a algo más parecido a: " ¿Existe una reducción directa / natural para contar los emparejamientos perfectos no bipartitos usando el permanente? "

Joshua Grochow

Buena idea. Ni siquiera pensé en eso. Gracias.

Derrick Stolee

Nitpicking: "Dado que encontrar una coincidencia perfecta en un gráfico no bipartito está en NP" → "Dado que contar coincidencias perfectas en un gráfico no bipartito está en #P"

Tsuyoshi Ito

Su punto de referencia es correcto, y consideré escribir eso, pero la forma en que lo escribí insinúa que la reducción aplica las reducciones de Cook ENTONCES de Valiant. Estoy buscando una reducción directa y eficiente.

Derrick Stolee el

\leq 4 n^{4}

$\leq 4n^4$

4 n^{4} + 1

$4n^4 +1$

S

$S$

S + 1

$S+1$

Respuestas:

Yo diría que una reducción "simple" a la coincidencia bipartita es altamente improbable. En primer lugar, daría un algoritmo para encontrar una coincidencia perfecta en un gráfico general utilizando el método húngaro. Por lo tanto, la reducción debe contener toda la complejidad del algoritmo de flor de Edmond. En segundo lugar, dará un LP compacto para un politopo de coincidencia perfecta y, por lo tanto, la reducción no debe ser simétrica (que se descarta como resultado de Yannakakis) e inherentemente muy complicada.

Mohit Singh
fuente

Todas estas son buenas razones por las cuales es poco probable que esto exista. Debería haber pedido refutaciones en la pregunta. Probablemente daré alguna recompensa por esta respuesta, a menos que alguien demuestre que estás equivocado.

Derrick Stolee

A pesar de que no era la respuesta que quería, encontré esta una respuesta muy satisfactoria.

Derrick Stolee

@MohitSingh ¿Podría por favor elaborar 'inexistencia de método húngaro para gráficos no bipartitos', 'qué contiene toda la complejidad del algoritmo de flor' y por qué esto daría 'LP compacto para una coincidencia perfecta y, por lo tanto, no debería ser simétrico'? ?

T ....

Obviamente, esto es un comentario y no una respuesta, pero todavía no tengo puntos de reputación aquí, lo siento mucho.

Para los gráficos sin puente cúbicos no bipartitos, existen exponencialmente muchas coincidencias perfectas, como conjeturaron Lovàsz y Plummer en los años 70. El trabajo está en preparación. Esto puede ser muy relevante para su pregunta, o tal vez no del todo.

Andrew D. King
fuente