Algoritmo de Karger para corte mínimo | Conjunto 2 (Análisis y Aplicaciones)

Hemos presentado y discutido a continuación el algoritmo de Karger en el conjunto 1.

1)  Initialize contracted graph CG as copy of original graph
2)  While there are more than 2 vertices.
      a) Pick a random edge (u, v) in the contracted graph.
      b) Merge (or contract) u and v into a single vertex (update 
         the contracted graph).
      c) Remove self-loops
3) Return cut represented by two vertices.

Como se discutió en la publicación anterior, el algoritmo de Karger no siempre encuentra el corte mínimo. En esta publicación, se analiza la probabilidad de encontrar un corte mínimo. 

Probabilidad de que el corte producido por el Algoritmo de Karger sea Min-Cut es mayor o igual a 1/(n ² ) 

Prueba: 
Sea un Min-Cut único del gráfico dado y que haya C aristas en el Min-Cut y las aristas sean {e ₁ , e ₂ , e ₃ , .. e _c }. El algoritmo de Karger produciría este Min-Cut si y solo si ninguno de los bordes en el conjunto {e ₁ , e ₂ , e ₃ , .. e _c } se elimina en iteraciones en el ciclo while principal del algoritmo anterior.

 

c is number of edges in min-cut
m is total number of edges
n is total number of vertices

S1 = Event that one of the edges in {e1, e2, 
     e3, .. ec} is chosen in 1st iteration.
S2 = Event that one of the edges in {e1, e2, 
     e3, .. ec} is chosen in 2nd iteration.
S3 = Event that one of the edges in {e1, e2, 
     e3, .. ec} is chosen in 3rd iteration.

..................
..................

The cut produced by Karger's algorithm would be a min-cut if none of the above
events happen.

So the required probability is P[S1' ∩ S2' ∩ S3' ∩  ............]

Probabilidad de que se elija un borde de corte mínimo en la primera iteración:

Let us calculate  P[S1']
P[S1]  = c/m
P[S1'] = (1 - c/m)

Above value is in terms of m (or edges), let us convert 
it in terms of n (or vertices) using below 2 facts.. 

1) Since size of min-cut is c, degree of all vertices must be greater 
than or equal to c. 

2) As per Handshaking Lemma, sum of degrees of all vertices = 2m

From above two facts, we can conclude below.
  n*c <= 2m
    m >= nc/2

  P[S1] <= c / (cn/2)
        <= 2/n

  P[S1] <= c / (cn/2)
        <= 2/n

  P[S1'] >= (1-2/n) ------------(1)

Probabilidad de que se elija un borde de corte mínimo en la segunda iteración:

P[S1' ∩  S2'] = P[S2' | S1' ] * P[S1']

In the above expression, we know value of P[S1'] >= (1-2/n)

P[S2' | S1'] is conditional probability that is, a min cut is 
not chosen in second iteration given that it is not chosen in first iteration

Since there are total (n-1) edges left now and number of cut edges is still c,
we can replace n by n-1 in inequality (1).  So we get.
  P[S2' | S1' ] >= (1 - 2/(n-1)) 

  P[S1' ∩  S2'] >= (1-2/n) x (1-2/(n-1))

Probabilidad de que se elija un borde de corte mínimo en todas las iteraciones:

P[S1' ∩  S2' ∩ S3'  ∩.......... ∩ Sn-2']

>= [1 - 2/n] * [1 - 2/(n-1)] * [1 - 2/(n-2)] * [1 - 2/(n-3)] *...
                              ... * [1 - 2/(n - (n-4)] * [1 - 2/(n - (n-3)]

>= [(n-2)/n] * [(n-3)/(n-1)] * [(n-4)/(n-2)] * .... 2/4 * 2/3

>= 2/(n * (n-1))
>= 1/n2 

¿Cómo aumentar la probabilidad de éxito? 

La probabilidad anterior de éxito del algoritmo básico es muy inferior. Por ejemplo, para un gráfico con 10 Nodes, la probabilidad de encontrar el corte mínimo es mayor o igual a 1/100. La probabilidad se puede aumentar mediante ejecuciones repetidas del algoritmo básico y devolver el mínimo de todos los cortes encontrados. 

Aplicaciones: 

1. En una situación de guerra, una parte estaría interesada en encontrar un número mínimo de enlaces que rompan la red de comunicación del enemigo. 
2. El problema de corte mínimo se puede utilizar para estudiar la confiabilidad de una red (menor número de bordes que pueden fallar). 
3. Estudio de optimización de redes (encontrar un caudal máximo). 
4. Problemas de agrupamiento (bordes como reglas de asociación) Problemas de coincidencia (un algoritmo NC para corte mínimo en gráficos dirigidos daría como resultado un algoritmo NC para coincidencia máxima en gráficos bipartitos) 
5. Problemas de coincidencia (un algoritmo NC para corte mínimo en gráficos dirigidos daría como resultado un algoritmo NC para coincidencia máxima en gráficos bipartitos).