O problema do Corte Máximo

Entrada

 - um grafo G=(V, E)
 
Solução

 - um corte (A, B), ou seja, uma partição de V em dois conjuntos que 
 
    - maximiza o número de arestas com uma ponta em cada conjunto (arestas cruzando o corte)



O prolema do Corte Máximo é um problema NP-Difícil

Um caso particular tratável deste problema que vale a pena destacar 

 - são os grafos bipartidos
 
Nestes grafos o problema pode ser resolvido usando Busca em Largura

Para entender o motivo, observe que

 - identificar se um grafo é bipartido pode ser feito em tempo polinomial 
 
    - usando justamente o algoritmo de Busca em Largura
 
 - como um grafo bipartido é composto por dois conjuntos independentes, i.e., que não tem arestas entre si
 
    - o corte ótimo será formado justamente por esses dois conjuntos



Antes de apresentar um algoritmo de busca local, vamos definir alguns conceitos

Dado um corte (A, B) e um vértice v, temos

 - c_v(A, B) = # arestas incidentes em v que cruzam o corte (A, B)
 
 - d_v(A, B) = # arestas incidentes em v que não cruzam o corte (A, B)
 
 - veja exemplo
 
Dizemos que duas soluções são vizinhas se elas diferem pela posição de apenas um vértice



Algoritmo de Busca Local

buscaLocalMaxCut(G=(V,E)) {
	
	seja (A, B) um corte arbitrário
	
	enquanto existir um vértice v tal que c_v(A, B) < d_v(A, B)
		troque o conjunto ao qual v pertence no corte (A, B)
	
	devolva (A, B)
}

Observe que em cada iteração o número de arestas no corte aumenta de 

	d_v(A, B) - c_v(A, B) > 0



Eficiência:

 - Como em cada iteração o corte aumenta de pelo menos uma aresta
 
 - E o corte máximo não pode ter mais que (n choose 2) = n(n-1)/2 = O(n^2) arestas
 
     - O algoritmo executa em O(n^2) iterações
 
 - Cada iteração leva O(n + m) passos, 
 
    - já que pode precisar verificar todos os vértices para encontrar aquele que vale a pena trocar de lado
	
	- e para contabilizar c_v(A, B) e d_v(A, B) precisa verificar as arestas que saem do vértice v
	
 - Portanto, o algoritmo é O(m n^2)
 
 - Mas algumas melhorias podem ser feitas para torná-lo assintoticamente mais eficiente, 
 
    - Em particular, podemos pré-calcular os valores de c_v e d_v para todo v no início, gastando O(n + m) = O(n^2)
	
	- Em cada iteração, buscamos por algum vértice com cv < dv em tempo O(n), no total das iterações gastando O(n^3)
	
	- Após a escolha do vértice em cada iteração, só alterarmos os valores de cv e dv dos vizinhos do vértice escolhido. Como um vértice tem no máximo O(n) vizinhos, ao longo de todas as iterações isso custa no máximo O(n^3)
	
 - Portanto, o algoritmo pode ser implementado com eficiência O(n^3)



Qualidade da Solução:

 - O algoritmo sempre encontra um corte com pelo menos 50% das arestas do ótimo.
 
Demonstração:

 - Considere um corte (A, B) devolvido pelo algoritmo
 
 - Temos que, para todo vértice v
 
	c_v(A, B) >= d_v(A, B)
	
 - Somando sobre todos os vértices temos
 
	\sum_{v \in V} c_v(A, B) >= \sum_{v \in V} d_v(A, B)
	
 - Ou seja, 
 
	2 * [# arestas cruzando o corte] >= 2 * [# arestas que não cruzam o corte]

 - Os fatores 2 aparecem porque tanto as arestas cruzando quanto as não cruzando são contadas duas vezes nos somatórios anteriores
 
    - Já que cada uma tem extremos em dois vértices e os somatórios são sobre os vértices

 - Para comparar com o número de arestas no corte (A, B) com o total de arestas do grafo, 
 
    - basta dividir os dois lados da inequação anterior por 2 
 
    - e somar o [# arestas cruzando o corte] dos dois lados
	
	   - já que |E| = [# arestas que não cruzam o corte] + [# arestas cruzando o corte]
	   
	[# arestas cruzando o corte] + [# arestas cruzando o corte] >= [# arestas que não cruzam o corte] + [# arestas cruzando o corte]
	
	2 * [# arestas cruzando o corte] >= |E|
	
 - Como o número de arestas no corte máximo OPT <= |E|, temos 
 
	[# arestas cruzando o corte] >= |E| / 2

 - Portanto, o algoritmo de busca local obtem uma solução 1/2-aproximada



Algoritmo Aleatorizado

 - Trata-se de um algoritmo muito simples que sorteia com probabilidade uniforme em que conjunto (A ou B) vai colocar cada vértice
 
Eficiência: \Theta(n)

Qualidade da Solução: Exp[# arestas cruzando o corte] = |E|/2

Demonstração:

 - Considere um corte (A, B) gerado aleatoriamente
 
 - Para cada aresta e = (u, v) definimos uma variável indicadora 
 
	Xe = 1 se e cruza o corte e Xe = 0 caso contrário
	
 - Observe que
 
	Exp[Xe] = Prob[Xe = 1] = 1/2
	
 - Pois e = (u, v) cruza o corte 

    - se u está em A (prob. 1/2) e v está em B (prob. 1/2) -> 1/2 * 1/2 = 1/4
	
	- ou v está em A (prob. 1/2) e u está em B (prob. 1/2) -> 1/2 * 1/2 = 1/4
	
	- probabilidade total = 1/4 + 1/4 = 1/2

 - Número esperado de arestas no corte (A, B) é 
 
	Exp[# arestas cruzando o corte] = Exp[\sum_{e \in E} Xe] 
	pela linearidade da esperança 	= \sum_{e \in E} Exp[Xe]
									= \sum_{e \in E} 1/2
									= |E|/2



Algoritmo Guloso

Também podemos pensar num algoritmo guloso que percorre os vértices numa ordem arbitrária, 

 - alocando cada vértice em A ou B de modo a maximizar o número de arestas no corte
 
Eficiência: \Theta(n + m), pois tem que percorrer todos os vértices e, para cada vértice, todas as arestas incidentes a ele

Qualidade da Solução: Esse algoritmo também é 1/2-aproximado, sendo possível realizar uma demonstração parecida com a que fizemos para o algoritmo de busca local



Versão do Corte Máximo Ponderado

 - Neste problema temos custos nas arestas
 
 - Os algoritmos anteriores continuam funcionando com as mesmas garantias de qualidade, embora as demonstrações tenham que ser levemente adaptadas para esse caso
 
 - Mas a eficiência do algoritmo de busca local é pior nesse caso
 
    - Isso porque, embora tenhamos garantia de que o valor do corte melhora a cada iteração do algoritmo
	
	- No caso ponderado o valor do corte máximo pode ser muito maior que n^2
	
	- De fato dependendo dos pesos das arestas
	
	- Assim, o número de iterações da busca local, e por consequência a eficiência do algoritmo também dependerão dos pesos das arestas