Corte Máximo

Um máximo de corte.

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

Referências

• Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer .

Corte máximo (versão de optimização) é o problema ND14 no Apêndice B (página 399).

• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, ISBN 0-7167-1045-5, W.H. Freeman .

Corte máximo (versão de decisão) é o problema ND16 no Apêndice A2.2.

Subgrafo bipartido máximo (versão de decisão) é o problema GT25 no Apêndice A1.2.

• Gaur, Daya Ram; Krishnamurti, Ramesh (2007), «LP rounding and extensions», in: Gonzalez, Teofilo F., Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC .
• Goemans, Michel X.; Williamson, David P. (1995), «Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming», Journal of the ACM, 42 (6): 1115–1145, doi:10.1145/227683.227684 .
• Hadlock, F. (1975), «Finding a Maximum Cut of a Planar Graph in Polynomial Time», SIAM J. Comput., 4 (3): 221–225, doi:10.1137/0204019 .
• Håstad, Johan (2001), «Some optimal inapproximability results», Journal of the ACM, 48 (4): 798–859, doi:10.1145/502090.502098 .
• Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike (2005), «Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs», SIAM Journal on Computing, 35 (1), doi:10.1137/s009753970139567x .
• Karp, Richard M. (1972), «Reducibility among combinatorial problems», in: Miller, R. E.; Thacher, J. W., Complexity of Computer Computation, Plenum Press, pp. 85–103 .
• Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), «Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?», SIAM Journal on Computing, 37 (1): 319–357, doi:10.1137/S0097539705447372 .
• Khuller, Samir; Raghavachari, Balaji; Young, Neal E. (2007), «Greedy methods», in: Gonzalez, Teofilo F., Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC .
• Mitzenmacher, Michael; Upfal, Eli (2005), Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge .
• Motwani, Rajeev; Raghavan, Prabhakar (1995), Randomized Algorithms, Cambridge .
• Newman, Alantha (2008), «Max cut», in: Kao, Ming-Yang, Encyclopedia of Algorithms, ISBN 978-0-387-30770-1, Springer, doi:10.1007/978-0-387-30162-4_219 .
• Papadimitriou, Christos H.; Yannakakis, Mihalis (1991), «Optimization, approximation, and complexity classes», Journal of Computer and System Sciences, 43 (3): 425–440, doi:10.1016/0022-0000(91)90023-X .
• Trevisan, Luca; Sorkin, Gregory; Sudan, Madhu; Williamson, David (2000), «Gadgets, Approximation, and Linear Programming», Proceedings of the 37th IEEE Symposium on Foundations of Computer Science: 617–626 .

Ler mais

• Barahona, Francisco; Grötschel, Martin; Jünger, Michael; Reinelt, Gerhard (1988), «An application of combinatorial optimization to statistical physics and circuit layout design», Operations Research, 36 (3): 493–513, JSTOR 170992, doi:10.1287/opre.36.3.493 .

Ligações externas

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "Maximum Cut", em "A compendium of NP optimization problems".
• Andrea Casini, Nicola Rebagliati (2012), "A Python library for solving Max Cut"