# Corte Máximo

Para um grafo, um corte máximo é um corte cujo tamanho é de pelo menos o tamanho de qualquer outro corte. O problema de encontrar um corte máximo em um grafo é conhecido como Problema do Corte-Máximo (Max-Cut).
O problema pode ser descrito simplesmente como segue. Deseja-se um subconjunto S do conjunto de vértices tal que o número de arestas entre S e o subconjunto complementar é tão grande quanto possível.
Há uma versão mais avançada do problema que se chama Corte-Máximo ponderado. Nesta versão cada aresta tem um número real, o seu peso, e o objetivo é maximizar não o número de arestas, mas o peso total das arestas entre S e seu complemento. O problema do Corte-Máximo ponderado é frequente, mas nem sempre, restrito a pesos não-negativos, porque pesos negativos podem alterar a natureza do problema.

## Complexidade computacional

O seguinte problema de decisão relacionado com o corte máximo tem sido amplamente estudado na teoria da ciência da computação:
    Dado um grafo G e um inteiro k, determinar se existe um corte de tamanho pelo menos k em G.
Esse problema é conhecido como sendo NP-completo. É fácil de ver que o problema está em NP: uma resposta sim é fácil provar através da apresentação de um corte grande o suficiente. A NP-completude do problema pode ser mostrada, por exemplo, por uma transformação a partir de 2-satisfatibilidade máxima (uma restrição do problema da satisfatibilidade máxima). A versão ponderada do problema de decisão foi um dos 21 problemas NP-completos de Karp; Karp mostrou a NP-completude por uma redução a partir do problema da partição.
A variante de otimização canônica do problema de decisão acima é geralmente conhecida como o Problema do Corte-Máximo ou MaxCut e é definido da seguinte forma:
    Dado um grafo G, encontre um corte máximo.

## Algoritmos de tempo polinomial

Como o Problema do MaxCut é NP-difícil, não há algoritmo de tempo polinomial conhecido para MaxCut em grafos gerais.
No entanto, em gráficos planares, o problema do Corte-Máximo é dual do problema de inspeção de rota (o problema de encontrar um caminho mais curto que passa por cada aresta de um grafo pelo menos uma vez), no sentido de que as arestas que não pertencem a um corte máximo de um grafo G são as duais de arestas que são duplicadas em uma volta de inspeção ótima do gráfico dual de G. A volta de inspeção ótima forma uma curva de auto-interseção que separa o plano em dois subconjuntos, o subconjunto de pontos para os quais o número de enrolamento da curva é o mesmo e o subconjunto para o qual o número de enrolamento é ímpar; estes dois subconjuntos formam um corte que inclui todas as arestas cujos duais aparecem em um número ímpar de vezes no caminho. O problema da inspeção de rota pode ser resolvido em tempo polinomial, e esta dualidade permite que o problema do corte máximo também seja resolvido em tempo polinomial para grafos planares. O problema da Bissetriz-Máxima é sabido, no entanto, ser NP-difícil.

## Algoritmos de aproximação

O problema de Corte-Máx é APX-difícil, o que significa que não há esquema de aproximação de tempo polinomial (PTAS), arbitrariamente perto da melhor solução, para ele, a menos que P = NP. Assim, cada algoritmo de aproximação de tempo polinomial atinge uma razão de aproximação estritamente menor do que um.
Há um simples algoritmo de 0.5-aproximação randomizado: para cada vértice lance uma moeda para decidir qual a metade da partição para atribuí-lo. Na expectância, metade das arestas são arestas de corte. Este algoritmo pode ser desrandomizado com o método das probabilidades condicionais; portanto, não é um simples 0.5-algoritmo de aproximação determinístico de tempo polinomial . Um tal algoritmo começa com uma partição arbitrária dos vértices do grafo dado $G=(V,E)$ e repetidamente se move de um vértice de cada vez de um lado da partição para o outro, melhorando a solução em cada etapa, até que nenhuma melhoria deste tipo possa ser feita. O número de iterações é no máximo $|E|$ porque o algoritmo melhora o corte de pelo menos uma aresta em cada etapa. Quando o algoritmo termina, pelo menos metade das arestas incidentes para cada vértice pertence ao corte, caso contrário, mover o vértice melhoraria o corte. Portanto, o corte inclui pelo menos $|E|/2$ arestas.
O algoritmo de aproximação de tempo polinomial para o Corte-Máx com a melhor razão conhecida de aproximação é um método de Goemans e Williamson usando programação semidefinida e arredondamento randomizado que atinge uma razão de aproximação de $\alpha \approx 0.878$, onde $\alpha ={\tfrac {2}{\pi }}\min _{0\leq \theta \leq \pi }{\tfrac {\theta }{1-\cos \theta }}$. Se a conjectura de jogos únicos é verdadeira, esta é a melhor razão de aproximação possível para o corte máximo. Sem tais suposições não comprovadas, foi provado ser NP-difícil para aproximar o valor de corte-máx com uma razão de aproximação melhor do que ${\tfrac {16}{17}}\approx 0.941$.

## Veja também

* Corte mínimo
* Mínimo de k-corte