Conjunto máximo independiente de un gráfico bipartito

19

Estoy tratando de encontrar el conjunto máximo independiente de un gráfico de biparita.

Encontré lo siguiente en algunas notas "13 de mayo de 1998 - Universidad de Washington - CSE 521 - Aplicaciones del flujo de red" :

Problema:

Dado un bipartito gráfico , encontrar un conjunto independiente que es lo más grande posible, donde y . Un conjunto es independiente si no hay bordes de entre los elementos del conjunto.G=(U,V,E)UVUUVVE

Solución:

Construya un gráfico de flujo en los vértices UV{s,t} . Para cada borde (u,v)E hay un borde de capacidad infinita de u a v . Para cada uU , hay un borde de capacidad de unidad de s a u , y para cada vV , hay un borde de capacidad de unidad de v a t .

Encontrar un corte capacidad finita (S,T) , con sS y tT . Let U=US y V=VT . El conjunto UV es independiente ya que no hay bordes de capacidad infinita que crucen el corte. El tamaño del corte es |UU|+|VV|=|U|+|V||UV|. Esto, para que el conjunto independiente sea lo más grande posible, hacemos que el corte sea lo más pequeño posible.

Entonces tomemos esto como el gráfico:

A - B - C
    |
D - E - F

Podemos dividir esto en un gráfico bipartito de la siguiente manera (U,V)=({A,C,E},{B,D,F})

Podemos ver por la búsqueda de fuerza bruta que la única máximo conjunto independiente es A,C,D,F . Probemos y analicemos la solución anterior:

Entonces la matriz de adyacencia de la red de flujo construida sería:

stABCDEFs00101010t00010101A1000000B01000C1000000D0100000E10000F0100000

Aquí es donde estoy atrapado, el corte de capacidad finita más pequeño que veo es trivial: (S,T)=({s},{t,A,B,C,D,E,F}) con una capacidad de 3)

El uso de este corte conduce a una solución incorrecta de:

U=US={}
V=VT={B,D,F}
UV={B,D,F}

Mientras que esperábamos UV={A,C,D,F} ? ¿Alguien puede detectar dónde me he equivocado en mi razonamiento / trabajo?

Andrew Tomazos
fuente
(S, T) = ({s, A, B, C}, {t, D, E, F}) tiene capacidad 2
1
@Brian hay un borde de capacidad infinita de B a E a través de tu corte, por lo que es una capacidad infinita.
Andrew Tomazos el
si entiendo esto correctamente, basado en la solución de fuerza bruta, necesita un corte donde S contiene A y C y T contiene D y F, lo que hace que su corte sea {s, A, C}, {t, D, F} . Ahora, ¿cómo construyes el corte?
njzk2
Además, esto se parece al Ford-Fulkerson, en el que los bordes tienen una capacidad de uno.
njzk2
Busque el algoritmo húngaro.
Patrik Vörös

Respuestas:

14

El complemento de un conjunto independiente máximo es una cubierta mínima de vértice.

Para encontrar una cobertura mínima de vértice en un gráfico bipartito, vea el teorema de König .

Jukka Suomela
fuente
2
Esto (tal vez) resuelve el problema pero no responde la pregunta.
Raphael
2
@Raphael: Estoy de acuerdo si eliminas la palabra "tal vez". :)
Jukka Suomela
1
Oh, estoy seguro de que resuelve el problema, pero no estoy seguro de si ayuda a Andrew a resolver su problema.
Raphael
3
Lo resolví como sugieres: HopcroftKarp -> coincidencia máxima -> Konigs Thereom -> Cubierta mínima de vértice -> Complemento -> Conjunto máximo independiente. Todavía me gustaría saber por qué el método de flujo descrito en mi pregunta no parece funcionar.
Andrew Tomazos
5

La solución dada es claramente incorrecta, como lo demuestra con el contraejemplo. Tenga en cuenta que el gráfico U + V es un componente conectado por los bordes de capacidad infinita. Por lo tanto, cada corte válido tendrá que contener todos A, B, C, D, E, F en el mismo lado.

Intentando rastrear de dónde vino la solución: http://www.cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf cita Network Flows, de Ahuja, Magnanti y Orlin para algunos de los problemas. Este libro no tiene derechos de autor y se puede descargar desde http://archive.org/details/networkflows00ahuj, pero no parece contener este problema y esta solución (buscando cada aparición de "bipartito").

Tenga en cuenta que el párrafo explicativo de la solución no muestra que el corte más pequeño del gráfico que construye corresponde al conjunto independiente máximo . Solo muestra una forma de obtener un conjunto independiente.

Y, sin embargo, puede ver qué intenta hacer el algoritmo. Esto es lo que corresponde al conjunto independiente máximo real en términos de su corte s, t:

Grafico

Se enfatiza el borde de capacidad infinita que rompe el algoritmo.

No estoy seguro de cómo arreglar el algoritmo para lo que se pretendía. ¿Quizás el costo de un borde infinito debería ser cero si va hacia atrás (es decir, dónde va de S a T, pero cruza de lado t a lado s)? Pero, ¿sigue siendo fácil encontrar el corte mínimo / flujo máximo con esta no linealidad? Además, al pensar en una forma de tender un puente desde la solución de @Jukka Suomela al algoritmo a partir de la pregunta, existe una dificultad en la que pasamos de la coincidencia máxima a la cobertura de vértice mínima: mientras que encontrar la coincidencia máxima se puede hacer mediante un flujo máximo -como algoritmo, ¿cómo se recupera la cobertura mínima de vértice utilizando un algoritmo de flujo? Como se describe aquí, después de encontrar la coincidencia máxima, los bordes entre U y V se dirigen para encontrar la cobertura mínima de vértice. Entonces, nuevamente, esto no muestra que una simple aplicación de min-cut / max-flow sea todo lo que se necesita para resolver este problema.

Evgeni Sergeev
fuente
2

STS

yu25x
fuente
1
Estoy de acuerdo con usted, pero ¿podría agregar más detalles, por ejemplo, una prueba de corrección completa del algoritmo de flujo y cómo se aplica el algoritmo en el ejemplo del OP?
xskxzr
La nota en esto tiene una breve prueba de corrección. cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf Por ejemplo, si observa la figura de Evgeni Sergeev arriba, todos los bordes deben dirigirse hacia abajo. Entonces, los únicos dos bordes fuera de S son (s, e) y (b, t), el borde rojo en negrita va hacia S y no debe contarse en el valor de corte.
yu25x
0

El corte debe estar en el flujo real, no en las capacidades. Como el flujo desde s es finito, cualquier corte {S, T} será finito. El resto es explicado anteriormente.

Talmon
fuente
1
¿Estás seguro? Los cortes generalmente dependen de las capacidades y, en cualquier caso, ya sabemos que el corte mínimo es finito, por lo que los cortes que son infinitos no parecen ser el problema.
David Richerby
0

UV

G{A,C,D,F}

Ajit Kumar
fuente