Coupe maximum

En théorie des graphes et en algorithmique, une coupe maximum est une 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'approximation.

Définition de l'objet et remarques préliminaires

Coupes et poids

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[1].

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[2].

É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[3], en le présentant comme un problème de satisfaction de contraintes.

Pour chaque arête ${\displaystyle (x_{i},x_{j})}$ du graphe, on considère l'équation ${\displaystyle x_{i}-x_{j}=1[2]}$. Le problème de la coupe maximum consiste alors à donner une affectation binaire aux variables ${\displaystyle (x_{i})_{i}}$, qui maximise le nombre d'équations vérifiées.

Résolution exacte

NP-complétude

Le problème de décision MAX-CUT est NP-complet[4]. 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[5], où l'on fait une réduction depuis le problème du séquençage de tâches en 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 graphes cordaux, aux split graphs, aux graphes tripartis, et co-bipartis[6].

Algorithmes efficaces pour des cas particuliers

Pour les graphes planaires, le problème peut être résolu en temps polynomial[7], car il se réduit à un problème de couplage maximum lui-même polynomial (par exemple avec l'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)[8].

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érandomisé pour obtenir un algorithme déterministe, grâce à la méthode des probabilités conditionnelles (en)[9].

Une meilleure approximation peut être atteinte en faisant appel à des techniques plus élaborées. L'algorithme de Goemans et Williamson, permet d'atteindre un ratio ${\displaystyle \alpha \approx 0.878}$, où plus exactement ${\displaystyle \alpha ={\tfrac {2}{\pi }}\min _{0\leq \theta \leq \pi }{\tfrac {\theta }{1-\cos \theta }}}$ en utilisant l'optimisation semi-définie positive[10],[11]. 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[12],[13].

Complexité et non-approximabilité

Le problème est difficile à approximer, plus précisément il est APX-hard[14]. En conséquence, il ne possède pas de PTAS, sauf si P=NP, mais il existe des 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[15]. En supposant seulement que P est différent de NP, on obtient une limite à 16/17[16],[17].

Cas particulier

Il existe un schéma d'approximation en temps polynomial dans le cas des graphes denses[18].

Autres modèles de calcul

Le problème a aussi été étudié du point de vue des algorithmes de streaming[19].

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[20].

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[21],[22].

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[23]. Ce problème peut lui aussi être décrit comme un problème de coupe maximum[24].

Bibliographie

Ouvrages généraux

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

• Samir Khuller, Balaji Raghavachari et Neal E. Young, « Greedy methods », dans Handbook of Approximation Algorithms and Metaheuristics, Chapman, 2007.

• Michael Mitzenmacher et Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge, 2005.

• (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge, New York et Melbourne, Cambridge University Press, 1995 (réimpr. 1997, 2000), 1^re éd., 476 p. (ISBN 978-0-521-47465-8, lire en ligne).

• Alantha Newman, « Max cut », dans Encyclopedia of Algorithms, Springer, 2008 (ISBN 978-0-387-30770-1, DOI 10.1007/978-0-387-30162-4_219)

Articles sur le problème algorithmique

• (en) Michel X. Goemans et David P. Williamson, « Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming », Journal of the ACM, vol. 42, n^o 6,‎ 1995, p. 1115-1145 (DOI 10.1145/227683.227684)

• (en) Subhash Khot, Guy Kindler, Elchanan Mossel et Ryan O'Donnell, « Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? », SIAM Journal on Computing, vol. 37, n^o 1,‎ 2007, p. 319-357 (DOI 10.1137/S0097539705447372)

Sur les applications

• Frédéric Meunier et Andras Sebo, « Parcours et coupes », dans Graphes et applications-vol. 2, JC Fournier, 2007 (lire en ligne)

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Maximum cut » (voir la liste des auteurs).

1. (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 2.4 (« Set Cover : Exercises ») p. 23.
2. (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 26 (« Semidefinite Programming »).
3. Cette remarque est présente dans le billet de Tim Gowers sur le prix Nevanlinna 2014. Il cite lui-même une présentation de Johan Håstad.
4. (en) Michael Garey et David S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979 (ISBN 0-7167-1045-5)
5. Richard M. Karp, « Reducibility among combinatorial problems », dans Complexity of Computer Computation, Plenum Press, 1972, p. 85-103
6. Hans Bodlaender et Klaus Jansen, « On the complexity of the maximum cut problem », dans STACS 94, 1994, p. 769-780
7. (en) F. Hadlock, « Finding a Maximum Cut of a Planar Graph in Polynomial Time », SIAM Journal on Computing, vol. 4,‎ 1975, p. 221–225 (DOI 10.1137/0204019, lire en ligne)
8. Voir l'article suivant, notamment pour la définition précise de "dense" : (en) Wenceslas Fernandez de la Vega et Marek Karpinski, « Polynomial time approximation of dense weighted instances of MAX-CUT », Random Structures and Algorithms, John Wiley \& Sons, Inc., vol. 16, n^o 4,‎ 2000, p. 314-332.
9. (en) Teofilo F. Gonzalez, Daya Ram Gaur et Ramesh Krishnamurti, Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC, 2007 (lire en ligne), « LP rounding and extensions », section 4.10.1
10. Article original : (Goemans et Williamson 1995)
11. Explication en français : (Meunier et Sebo 2007).
12. Sanjeev Arora, Elad Hazan et Satyen Kale, « The Multiplicative Weights Update Method: a Meta-Algorithm and Applications », Theory of Computing, vol. 8, n^o 1,‎ 2012, p. 121-164 (lire en ligne).
13. Philip N. Klein et Hsueh-I Lu, « Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING », dans Proceedings of the Twenty-Eighth Annual {ACM} Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, 1996 (DOI 10.1145/237814.237980), p. 338-347
14. (en) Christos H. Papadimitriou et Mihalis Yannakakis, « Optimization, approximation, and complexity classes », Journal of Computer and System Sciences, vol. 43, n^o 3,‎ 1991, p. 425–440 (DOI 10.1016/0022-0000(91)90023-X)
15. (en) Subhash Khot, Guy Kindler, Elchanan Mossel et Ryan O'Donnell, « Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? », SIAM Journal on Computing, vol. 37, n^o 1,‎ 2007, p. 319-357 (DOI 10.1137/S0097539705447372).
16. (en) Johan Håstad, « Some optimal inapproximability results », Journal of the ACM, vol. 48,‎ 2001, p. 798–859 (DOI 10.1145/502090.502098)
17. (en) Luca Trevisan, Gregory Sorkin, Madhu Sudan et David Williamson, « Gadgets, Approximation, and Linear Programming », dans Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, 2000, p. 617-626.
18. Sanjeev Arora, David R. Karger et Marek Karpinski, « Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems », J. Comput. Syst. Sci., vol. 58, n^o 1,‎ 1999, p. 193-210
19. Michael Kapralov, Sanjeev Khanna et Madhu Sudan, « Streaming Lower Bounds for Approximating {MAX-CUT} », dans Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA) San Diego, CA, USA, January 4-6, 2015,, 2015 (lire en ligne), p. 1263-1282
20. Voir (en) Francisco Barahona, Martin Grötschel, Michael Jünger et Gerhard Reinelt, « An application of combinatorial optimization to statistical physics and circuit layout design », Operations Research, vol. 36, n^o 3,‎ 1988, p. 493-513 (DOI 10.1287/opre.36.3.493, JSTOR 170992).
21. Cette application est tirée de (Meunier et Sebo 2007), qui contient une explication plus complète.
22. Cette application a été décrite pour la première fois dans : (en) Francisco Barahona, R Maynard, R Rammal et JP Uhry, « Morphology of ground states of two-dimensional frustration model », Journal of Physics A: Mathematical and General, vol. 15, n^o 2,‎ 1982, p. 673
23. Voir Ron Yair Pinter, « Optimal layer assignment for interconnect », Journal of VLSI and computer systems, Computer Science Press, vol. 1, n^o 2,‎ 1984, p. 123-137.
24. Voir (Meunier et Sebo 2007). La dénomination "problème de Pinter", provient elle aussi de ce document.

Liens externes

• (en) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski et Gerhard Woeginger, « Maximum Cut », sur A compendium of NP optimization problems, 2000.
• Un billet de Luca Trevisan sur son blog, à propos de Max-cut et le lien avec la théorie spectrale des graphes.
• 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 Mathématiques, l'explosion continue, FSMP, SFS, SMF, SMAI, 2013
• Pierre Pansu, « Le découpage des graphes », sur Images des Maths, 10 novembre 2011 (consulté le 23 juin 2014)