Voir la source de Coupe maximum

En [[théorie des graphes]] et en [[algorithmique]], une '''coupe maximum''' est une [[coupe (théorie des graphes)|coupe]] contenant au moins autant d'arêtes que n'importe quelle autre coupe. Une extension de la définition consiste à considérer des poids associés aux arêtes. On considère alors la coupe ayant le poids total maximum.

Les coupes maximums sont des objets utiles notamment en [[physique théorique]] et en électronique. Mais elles sont surtout connues pour le problème algorithmique qui consiste à trouver une coupe maximum, appelé couramment ''MAX-CUT'', un problème relativement bien étudié, notamment dans le contexte de l'[[algorithme d'approximation|approximation]].

== Définition de l'objet et remarques préliminaires ==
=== Coupes et poids ===
[[Fichier:Max-cut.svg|vignette|Une coupe maximum]]

Étant donné un graphe, et des poids sur les arêtes, une coupe peut-être décrite comme un ensemble de sommets, et le poids de la coupe est alors la somme des poids des arêtes ayant une extrémité à l'intérieur de cet ensemble et l'autre à l'extérieur. Une coupe est maximum si son poids est maximum (parmi toutes les coupes).

Un cas particulier est celui de la coupe de cardinalité maximum, qui correspond à des poids égaux à 1. Dans ce cas le poids d'une coupe est simplement le nombre d'arêtes.

=== Remarques ===
Remarquons qu'''a priori'' il peut y avoir plusieurs coupes maximums, c'est-à-dire plusieurs coupes différentes mais de même cardinal : le cardinal maximum.

On peut aussi considérer l'objet « jumeau » qui est la [[coupe minimum]], et qui a des propriétés complètement différentes, par exemple la relation donnée par le [[théorème flot-max/coupe-min]].

Une généralisation de l'objet est la ''k''-coupe maximum : on considère alors non plus deux composantes mais ''k'' composantes<ref>{{Approximation algorithms (Vazirani)|numéro chapitre=2.4|titre chapitre=Set Cover : Exercises}} {{p.|23}}.</ref>.

== Définition du problème algorithmique ==
=== Définition classique ===
On considère le problème d'[[optimisation combinatoire]] suivant :
: Étant donné un graphe ''G'', trouver une coupe maximum.

Et le [[problème de décision]] associé :
: Étant donné un graphe ''G'' et un entier ''k'', existe-t-il une coupe de poids au moins ''k'' ?

On considère le plus souvent des poids positifs rationnels<ref>{{Approximation algorithms (Vazirani)|numéro chapitre=26|titre chapitre=Semidefinite Programming}}.</ref>.

=== Écriture en équation ===
Le problème peut-être reformulé sous forme d'équations à satisfaire. Cette écriture permet notamment de rapprocher le problème de la [[conjecture des jeux uniques]]<ref>Cette remarque est présente dans le [http://gowers.wordpress.com/2014/08/20/khot-laudatio/#more-5631 billet] de [[Timothy Gowers|Tim Gowers]] sur le [[prix Nevanlinna]] 2014. Il cite lui-même une [http://www.math.kth.se/~dirocco/ML2011/CIAMWORKSHOP/24/presentation2.pdf présentation] de [[Johan Håstad]].</ref>, en le présentant comme un [[problème de satisfaction de contraintes]].

Pour chaque arête <math>(x_i,x_j)</math> du graphe, on considère l'équation <math>x_i - x_j = 1 [2]</math>. Le problème de la coupe maximum consiste alors à donner une affectation binaire aux variables <math>(x_i)_i</math>, qui maximise le nombre d'équations vérifiées.

== Résolution exacte ==
=== NP-complétude ===
Le problème de décision MAX-CUT est [[Problème NP-complet|NP-complet]]<ref>{{Garey Johnson NP}}</ref>. Le problème d'optimisation MAX-CUT est NP-dur. La version dans laquelle les arêtes ont des poids fait partie des [[21 problèmes NP-complets de Karp]]<ref>{{Chapitre
 | nom1 = Karp | prénom1 = Richard M. | lien auteur1 = Richard Karp
 | titre ouvrage = Complexity of Computer Computation
 | titre chapitre = Reducibility among combinatorial problems
 | éditeur = Plenum Press
 | passage = 85-103
 | année=1972
}}</ref>, où l'on fait une [[réduction (complexité)|réduction]] depuis le problème du [[séquençage de tâches]] en [[Théorie de l'ordonnancement|ordonnancement]] , lui-même réduit du [[problème du sac à dos]].

Le problème de décision reste NP-complet si l'on se restreint aux [[graphe cordal|graphes cordaux]], aux ''[[Graphe scindé|split graphs]]'', aux graphes tripartis, et co-bipartis<ref>
{{Chapitre
 |titre chapitre=On the complexity of the maximum cut problem
 |auteur1=Hans Bodlaender | auteur2= Klaus Jansen
 |titre ouvrage=STACS 94
 |passage=769-780
 |année=1994
}}</ref>.

=== Algorithmes efficaces pour des cas particuliers ===
Pour les [[graphe planaire|graphes planaires]], le problème peut être résolu en [[P (complexité)|temps polynomial]]<ref>{{Article
 |langue=en
 |prénom1=F.|nom1=Hadlock
 |titre=Finding a Maximum Cut of a Planar Graph in Polynomial Time
 |périodique = SIAM Journal on Computing
 |année=1975
 |volume=4|passage=221–225
 |doi=10.1137/0204019
 |lire en ligne = http://web.eecs.umich.edu/~pettie/matching/Hadlock-maxcut-planar-graph-reduction-to-T-join.pdf}}</ref>, car il se réduit à un problème de [[Couplage (théorie des graphes)|couplage]] maximum lui-même polynomial (par exemple avec l'[[algorithme d'Edmonds pour les couplages|algorithme d'Edmonds]]). C'est un résultat important pour les applications.

Dans le cas des graphes denses, on peut définir un [[schéma d'approximation en temps polynomial]] (''PTAS'')<ref>Voir l'article suivant, notamment pour la définition précise de "dense" : {{Article
 | langue= en
 | nom1 = Fernandez de la Vega | prénom1 = Wenceslas
 | nom2 = Karpinski |prénom2 = Marek
 | titre=Polynomial time approximation of dense weighted instances of MAX-CUT
 | périodique = Random Structures and Algorithms
 | volume= 16 | numéro= 4 | passage=314-332
 | année = 2000
 | éditeur = John Wiley \& Sons, Inc.
}}.</ref>.

== Approximation ==
=== Algorithmes ===
Un [[algorithme probabiliste]] très simple permet d'obtenir un ratio 1/2 : chaque nœud choisit indépendamment et uniformément de quel côté de la coupe il va être. Chaque arête a une probabilité 1/2 d'être dans la coupe, ainsi on obtient au moins la moitié de la valeur de la coupe maximum en espérance. Cet algorithme peut-être [[dérandomisation|dérandomisé]] pour obtenir un [[algorithme déterministe]], grâce à la {{Lien|langue=en|trad=Method of conditional probabilities|fr=méthode des probabilités conditionnelles}}<ref>{{Ouvrage
 |langue=en
 |prénom1=Teofilo F.|nom1=Gonzalez
 |prénom2=Daya Ram|nom2=Gaur
 |prénom3=Ramesh|nom3=Krishnamurti
 |titre=Handbook of Approximation Algorithms and Metaheuristics
 |titre chapitre = LP rounding and extensions
 |éditeur=Chapman &amp; Hall/CRC
 |année=2007
 |lire en ligne = https://books.google.fr/books?id=QK3_VU8ngK8C&printsec=frontcover&dq=Handbook+of+Approximation+Algorithms+and+Metaheuristics&hl=fr&sa=X&ei=U7H3Uv6zA4ic0QWjvoFg&ved=0CDIQ6AEwAA#v=onepage&q=Handbook%20of%20Approximation%20Algorithms%20and%20Metaheuristics&f=false
}}, section 4.10.1</ref>.

Une meilleure approximation peut être atteinte en faisant appel à des techniques plus élaborées. L'algorithme de [[Michel Goemans|Goemans]] et [[David P. Williamson|Williamson]], permet d'atteindre un ratio <math>\alpha \approx 0.878</math>, où plus exactement <math>\alpha = \tfrac{2}{\pi} \min_{0 \le \theta \le \pi} \tfrac{\theta}{1 - \cos \theta}</math> en utilisant l'[[optimisation SDP|optimisation semi-définie positive]]<ref>Article original : {{harv|Goemans|Williamson|1995}}</ref>{{,}}<ref>Explication en français : {{harv|Meunier|Sebo|2007}}.</ref>. Il est possible d'utiliser une approximation de la solution du problème SDP pour obtenir un algorithme plus rapide ; cette approximation utilise une forme de la [[méthode des poids multiplicatifs]]<ref name=AroraHK>
{{article
| titre=The Multiplicative Weights Update Method: a Meta-Algorithm and Applications
| auteur1= [[Sanjeev Arora]] | auteur2= Elad Hazan |auteur3= Satyen Kale
| périodique=[[Theory of Computing]]
| volume=8 | numéro=1| passage=121-164
|année =2012
|lire en ligne= https://theoryofcomputing.org/articles/v008a006/v008a006.pdf
}}.</ref>{{,}}<ref>
{{chapitre
 |auteur1= Philip N. Klein |auteur2 =  Hsueh-I Lu
 |titre chapitre     = Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING
 | titre ouvrage = Proceedings of the Twenty-Eighth Annual {ACM} Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996
 | passage     = 338-347
 | année      = 1996
 | doi       = 10.1145/237814.237980
}}
</ref>.

=== Complexité et non-approximabilité ===
Le problème est difficile à approximer, plus précisément il est [[APX (complexité)|APX-hard]]<ref>
{{Article
 | langue = en
 | nom1=Papadimitriou | prénom1=Christos H. | lien auteur1=Christos Papadimitriou
 | auteur2=[[Mihalis Yannakakis]]
 | titre=Optimization, approximation, and complexity classes
 | périodique=Journal of Computer and System Sciences
 | année=1991
 | volume=43 | numéro=3 | pages=425–440
 | doi=10.1016/0022-0000(91)90023-X
}}</ref>. En conséquence, il ne possède pas de PTAS, sauf si [[problème P = NP|P=NP]], mais il existe des [[algorithme d'approximation|algorithmes d'approximation]] ayant des ratios constants.

[[Subhash Khot]], Guy Kindler, Elchanan Mossel et Ryan O'Donnell ont montré qu'en supposant la [[conjecture des jeux uniques]] (''Unique Games Conjecture'') l'approximation de Goemans et Williamson est optimale<ref>{{Article  | langue = en  | auteur1=[[Subhash Khot]] | nom2=Kindler | prénom2=Guy  | nom3=Mossel | prénom3=Elchanan  | nom4=O'Donnell | prénom4=Ryan  | titre = Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?  | périodique=SIAM Journal on Computing  | volume=37  | numéro=1  | année=2007  | passage=319-357  | doi=10.1137/S0097539705447372}}.</ref>. En supposant seulement que [[problème P=NP|P est différent de NP]], on obtient une limite à 16/17<ref>
{{Article
 |langue=en
 |auteur1=[[Johan Håstad]]
 |titre=Some optimal inapproximability results
 |périodique = Journal of the ACM
 |année=2001
 |volume=48 |passage=798–859
 |doi=10.1145/502090.502098}}
</ref>{{,}}<ref>
{{Chapitre
 | langue = en
 | nom1=Trevisan | prénom1=Luca
 | nom2=Sorkin | prénom2=Gregory
 | auteur3=[[Madhu Sudan]]
 | nom4=Williamson | prénom4=David | lien auteur4=David P. Williamson
 | titre chapitre = Gadgets, Approximation, and Linear Programming
 | titre ouvrage = Proceedings of the 37th IEEE [[Symposium on Foundations of Computer Science]]
 | année=2000
 | passage = 617-626
}}.</ref>.

=== Cas particulier ===

Il existe un [[schéma d'approximation en temps polynomial]] dans le cas des [[graphe dense|graphes denses]]<ref>
{{article
 | auteur1    = [[Sanjeev Arora]] | auteur2= David R. Karger |auteur3= Marek Karpinski
 | titre     = Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems
 | périodique   = J. Comput. Syst. Sci.
 | volume    = 58 | numéro    = 1 | passage     = 193-210
 | année      = 1999}}</ref>.

== Autres modèles de calcul ==
Le problème a aussi été étudié du point de vue des [[Algorithme de fouille de flots de données|algorithmes de streaming]]<ref>
{{Chapitre
| auteur1 = Michael Kapralov
| auteur2 = Sanjeev Khanna
| auteur3 = [[Madhu Sudan]]
| titre chapitre    = Streaming Lower Bounds for Approximating <nowiki>{</nowiki>MAX-CUT<nowiki>}</nowiki>
| titre ouvrage = Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA) San Diego, CA, USA, January 4-6, 2015,
| passage     = 1263-1282
| année     = 2015
|lire en ligne = https://arxiv.org/abs/1409.2138}}</ref>.

== Applications ==
La coupe maximum est un objet assez naturel qui trouve des applications en [[physique statistique]] et en [[intégration à très grande échelle]] notamment<ref>Voir {{Article
 |langue = en
 |nom1=Barahona|prénom1=Francisco
 |auteur2=[[Martin Grötschel]]
 |nom3=Jünger|prénom3=Michael
 |nom4=Reinelt |prénom4=Gerhard
 |titre=An application of combinatorial optimization to statistical physics and circuit layout design
 |périodique = Operations Research
 |volume=36 |numéro=3
 |année=1988
 |passage = 493-513
 |doi=10.1287/opre.36.3.493
 |jstor=170992
}}.</ref>.

=== Modèle d'Ising ===
L'une des applications est le [[modèle d'Ising]], les sommets du graphe représentent les atomes et les arêtes représentent les interactions non négligeables. Chaque [[atome]] a un [[spin]], ''up'' ou ''down'', et les interactions définissent alors des poids. Les coupes maximums correspondent alors aux états d'énergie minimale<ref>Cette application est tirée de {{harv|Meunier|Sebo|2007}}, qui contient une explication plus complète.</ref>{{,}}<ref>Cette application a été décrite pour la première fois dans : {{Article
 | langue = en
 | nom1 = Barahona | prénom1 = Francisco
 | nom2 = Maynard | prénom2 = R
 | nom3 = Rammal |prénom3 = R
 | nom4 = Uhry |prénom4 = JP
 | titre=Morphology of ground states of two-dimensional frustration model
 | périodique = Journal of Physics A: Mathematical and General
 | volume= 15 | numéro = 2 | passage = 673
 | année = 1982
}}</ref>.

=== Problème de Pinter ===
Le problème de Pinter consiste à placer des fils des deux côtés d'une plaque, sans intersections, en minimisant le nombre de fils traversant la plaque<ref>Voir {{Article
 | nom1 = Pinter | prénom1 = Ron Yair
 | titre= Optimal layer assignment for interconnect
 | périodique = Journal of VLSI and computer systems
 | volume=1 |numéro=2 | passage= 123-137
 | année = 1984
 | éditeur = Computer Science Press
}}.</ref>. Ce problème peut lui aussi être décrit comme un problème de coupe maximum<ref>Voir {{harv|Meunier|Sebo|2007}}. La dénomination "problème de Pinter", provient elle aussi de ce document.</ref>.

== Bibliographie ==
=== Ouvrages généraux ===
* {{Ouvrage
 |langue=en
 |prénom1=Giorgio|nom1=Ausiello
 |prénom2=Pierluigi|nom2=Crescenzi
 |prénom3=Giorgio |nom3=Gambosi
 |prénom4=Viggo|nom4=Kann
 |prénom5=Alberto|nom5=Marchetti-Spaccamela
 |prénom6=Marco|nom6=Protasi
 |titre=Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties
 |éditeur=Springer
 |année=2003}}f

* {{Chapitre
 | nom1=Khuller | prénom1=Samir
 | nom2=Raghavachari | prénom2=Balaji
 | nom3=Young | prénom3=Neal E.
 | titre chapitre = Greedy methods
 | titre ouvrage = Handbook of Approximation Algorithms and Metaheuristics
 | éditeur = Chapman
 | année = 2007}}.

* {{Ouvrage
 | nom1=Mitzenmacher | prénom1=Michael
 | nom2=Upfal | prénom2=Eli
 | titre=Probability and Computing: Randomized Algorithms and Probabilistic Analysis
 | éditeur=Cambridge
 | année=2005
}}.

* {{Randomized Algorithms (Motwani et Raghavan)}}.

* {{Chapitre
 | nom1=Newman | prénom1=Alantha
 | titre chapitre = Max cut
 | titre ouvrage = Encyclopedia of Algorithms
 | éditeur = Springer
 | année=2008
 | doi=10.1007/978-0-387-30162-4_219
 | isbn=978-0-387-30770-1
}}

=== Articles sur le problème algorithmique ===
* {{Article
 |langue=en
 |prénom1=Michel X.|nom1=Goemans | lien auteur1 = Michel Goemans
 |prénom2=David P.|nom2=Williamson | lien auteur2 =David P. Williamson
 |titre=Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
 | périodique  = [[Journal of the ACM]]
 | année  = 1995
 | volume = 42 | numéro = 6 | pages  = 1115-1145
 | doi  = 10.1145/227683.227684}}

* {{Article
 | langue = en
 | auteur1=[[Subhash Khot]]
 | nom2=Kindler | prénom2=Guy
 | nom3=Mossel | prénom3=Elchanan
 | nom4=O'Donnell | prénom4=Ryan
 | titre = Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?
 | périodique=SIAM Journal on Computing
 | volume=37
 | numéro=1
 | année=2007
 | passage=319-357
 | doi=10.1137/S0097539705447372}}

=== Sur les applications ===
* {{Chapitre
 | nom1 = Meunier | prénom1 = Frédéric
 | nom2 = Sebo | prénom2 = Andras
 | titre chapitre=Parcours et coupes
 | titre ouvrage = Graphes et applications-vol. 2
 | éditeur = JC Fournier
 | année = 2007
 | lire en ligne = http://cermics.enpc.fr/~meuniefr/hermes13dec.pdf
}}

== Notes et références ==
{{Traduction/Référence|en|Maximum cut|581715705}}
{{Références}}

== Liens externes ==
* {{Lien web| langue = en| url = http://www.nada.kth.se/~viggo/wwwcompendium/node85.html | titre = Maximum Cut | année = 2000 | site = A compendium of NP optimization problems | auteur1 = Pierluigi Crescenzi | auteur2 = Viggo Kann | auteur3 = Magnús Halldórsson | auteur4 = [[Marek Karpinski]] | auteur5 = [[Gerhard Woeginger]]}}.
* [http://lucatrevisan.wordpress.com/2008/06/13/max-cut-and-the-smallest-eigenvalue/ Un billet] de [[Luca Trevisan]] sur son blog, à propos de Max-cut et le lien avec la [[théorie spectrale des graphes]].
* [http://www.liafa.jussieu.fr/~nschaban/publications/2012/2012-Maths-PansuSchabanel.pdf Couper, attendrir, trancher, réduire: un conte culinaire sur la résolution informatique des problèmes difficiles], une métaphore culinaire du problème et de sa résolution approchée, par Nicolas Schabanel et [[Pierre Pansu]], dans {{Ouvrage
 | titre = Mathématiques, l'explosion continue
 | année = 2013
 | éditeur = FSMP, SFS, SMF, SMAI
}}
* {{Lien web|url=http://images.math.cnrs.fr/Le-decoupage-des-graphes.html |titre= Le découpage des graphes | auteur = Pierre Pansu|date=10 novembre 2011|site= [[Images des mathématiques|Images des Maths]] |consulté le=23 juin 2014}}

{{Palette 21 problèmes NP-complets de Karp}}

{{Portail|mathématiques|Informatique théorique}}

[[Catégorie:Concept en théorie des graphes]]
[[Catégorie:Problème NP-complet]]