Complejidad de contar coincidencias en un gráfico bipartito

Puede que me falte algo obvio, pero no puedo encontrar referencias sobre la complejidad de contar coincidencias (no coincidencias perfectas) en gráficos bipartitos. Aquí está el problema formal:

Entrada: un gráfico bipartito con $G = (U, V, E)$ $E \subseteq U \times V$
Salida: el número de emparejamientos de , donde un matchings es un subconjunto de tal manera que no hay que se produce en dos bordes de . $G$ $F \subseteq E$ $v \in U \sqcup V$ $F$

¿Cuál es la complejidad de este problema? ¿Es # P-duro?

Es bien sabido que contar coincidencias perfectas en gráficos bipartitos es # P-difícil, y se sabe que contar coincidencias de gráficos arbitrarios (o incluso gráficos planas de 3 regulares) es # P-difícil en este artículo , pero no lo hice No encuentre nada acerca de contar coincidencias no perfectas en gráficos bipartitos.

counting-complexity matching bipartite-graphs a3nm
fuente

Parece haber un problema en este algoritmo, hay casos en el resultado en que no todos los nodos del lado izquierdo o derecho están incluidos en la solución 2sat, por lo tanto, el algoritmo de conteo exacto no funciona. ¿Alguien sabe un algoritmo para soluciones de coincidencia bipartita máximo único que se derivó utilizando una reducción a 2sat?

user3700810

Respuestas:

El problema de contar tales coincidencias "imperfectas" en gráficos bipartitos es # P-completo.
Esto ha sido probado por el propio Les Valiant, en la página 415 del documento.

Leslie G. Valiant
La complejidad de los problemas de enumeración y confiabilidad
SIAM J. Comput., 8 (3), 410–421

Gamow
fuente

Se ve bien, gracias! No sé por qué este simple hecho no se mencionó claramente en la página de Wikipedia (o aparentemente en otra parte de la Web). Mejoré Wikipedia en consecuencia: en.wikipedia.org/w/… ¡ Gracias de nuevo!

a3nm

Una semana en mi clase de teoría de la complejidad en la universidad, nuestro único problema de tarea fue demostrar que # 2-SAT era # P-completo, reduciendo de #BIPARTITE PERFECTO ENCUENTRO. Nadie pudo resolverlo, incluso cuando finalmente todos nos unimos para trabajar en ello.

En la siguiente clase, el profesor se sorprendió de lo difícil que todos lo habíamos encontrado y presentó su prueba. Estaba mal. Afortunadamente, una cookie inteligente fue capaz de dar la reducción correcta, lo cual fue absolutamente loco y asquerosamente complicado. Por cierto, el profesor tiene un Premio Turing :)

De todos modos, aunque mis compañeros de clase y yo no pudimos resolver ese problema, pudimos resolver el problema más fácil de reducir de #BIPARTITE MATCHING a # 2-SAT, así que aquí está la prueba que obtuve hace unos años.

Teorema. #BIPARTITE Matching # 2-SAT. $≤_p$

Prueba . Sea una instancia de #BIPARTITE MATCHING. Deje que los conjuntos de particiones sean $G = (V,E)$ (de modo y ).

A = {a_{i} ∣ i \in [n]}, B = {b_{i} ∣ i \in [m]}

$A = \{a_i \mid i∈[n]\}, \quad B = \{b_i \mid i∈[m]\}$

| A | = n

$|A|=n$

| B | = m

$|B|=m$

Ahora reducimos a una fórmula 2SAT , de modo que cada asignación satisfactoria de sea una coincidencia de , y viceversa. Para comenzar, para cada arista cree una variable . La idea es que establecer la variable en TRUE corresponde a que el borde esté en la coincidencia. Para cada vértice , cree las expresiones 2SAT Para que se satisfaga, todos menos uno como tienen que ser falsos. Para ver esto, asuma que tanto $G$ $φ$ $φ$ $G$ $a_ib_j ∈ E$ $x_{ij}$ $x_{ij}$ $a_ib_j$ $i$

A_{i} = \underset{j < k}{⋀} (\neg x_{i j} \lor \neg x_{i k}), B_{i} := \underset{j < k}{⋀} (\neg x_{j i} \lor \neg x_{k i})

$A_i = \bigwedge_{j < k} (¬x_{ij} ∨ ¬x_{ik}), \quad B_i := \bigwedge_{j<k} (¬x_{ji} ∨ ¬x_{ki})$

A_{i}

$A_i$

x_{i j}

$x_{ij}$

x_{i j}

$x_{ij}$ y son verdaderas. Entonces es falso, y también lo es . Lo mismo vale para . Dejando que tenemos que se satisface si y solo si cada vértice en incide como máximo en un borde que elegimos, y así Los bordes forman una coincidencia.

x_{i k}

$x_{ik}$

(\neg x_{i j} \lor \neg x_{i k})

$(¬x_{ij} ∨ ¬x_{ik})$

A_{i}

$A_i$

B_{i}

$B_i$

C = ⋀_{i = 1}^{n} A_{i} \land ⋀_{i = 1}^{m} B_{i}

$C = \bigwedge_{i=1}^n A_i ∧ \bigwedge_{i=1}^m B_i$

C

$C$

G

$G$

cabeza de jardín
fuente

Creo que me falta algo aquí. Esto parece mostrar que una instancia arbitraria de #BIPARTITE_MATCHING puede codificarse como una instancia de # 2-SAT. Pero, esperaba que intentara demostrar que una instancia arbitraria de # 2-SAT puede codificarse como una instancia de #BIPARTITE_MATCHING, ¿no?

mhum

Vaya, tienes razón. Esto fue eliminado de un viejo problema de tarea y en realidad no tenía la pregunta escrita, solo mi respuesta. El problema debe haber sido demostrar que # 2-SAT era # P-Complete, sabiendo que # BIPARTITE-PERFECT-MATCHING era # P-complete. Lo editaré

cabeza de jardín

@gardenhead: ¡Gracias por tu respuesta! Esto es interesante pero no creo que esté muy relacionado con mi pregunta, ¿verdad? Esto solo muestra que # BIPARTITE-MATCHING está en #P, lo cual no es una gran sorpresa.

a3nm

La reducción en esta respuesta parece ser correcta, aunque parece no estar relacionada con la pregunta. Sin embargo, no entiendo el comentario de @ a3nm, ni sigo la historia en el prefacio de la respuesta (que confunde tres reducciones diferentes).

András Salamon

Descubrí cómo reducir # MONO-2SAT a #BIPARTITE PERFECTO A JUEGO, pero la prueba no es tan simple: P.