Coupe maximum

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes et en algorithmique, une coupe maximum est une coupe contenant au moins autant d'arêtes que n'importe quel 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 connus 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 et propriétés[modifier | modifier le code]

Une coupe maximum

Une coupe peut-être décrite comme un ensemble de sommets, et le cardinal de la coupe est alors le nombre d'arêtes ayant une extrémité à l'intérieur cet ensemble et l'autre à l'extérieur. Une coupe est maximum si son cardinal est maximum.

Remarquons qu'a priori il peut y avoir plusieurs coupes maximums, ie. 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.

Problème algorithmique[modifier | modifier le code]

On considère le problème d'optimisation combinatoire suivant :

Étant donné un graphe G, trouver coupe maximum.

que l'on transforme en le problème de décision :

Étant donné un graphe G et un entier k, existe-t-il une coupe de cardinal au moins k ?

Complexité[modifier | modifier le code]

Le problème MAX-CUT est NP-complet[1]. La version dans laquelle les arêtes ont des poids fait partie des 21 problèmes NP-complets de Karp[2].

Le problème est aussi difficile à approximer, plus précisément il est APX-hard (en)[3].

Algorithmes d'approximation[modifier | modifier le code]

Le problème ne possède pas de schéma d'approximation en temps polynomial (PTAS), sauf si P=NP, mais il existe des algorithmes d'approximation ayant des ratio constants.

Un algorithme probabiliste très simple permet d'obtenir un ratio 0.5 : chaque nœud choisit indépendamment et uniformément de quel coté 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é 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)[4].

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 \alpha \approx 0.878, où plus exactement \alpha = \tfrac{2}{\pi} \min_{0 \le \theta \le \pi} \tfrac{\theta}{1 - \cos \theta} en utilisant l'optimisation semi-définie positive[5].

Subhash Khot, Guy Kindler, Elchanan Mossel et Ryan O'Donnell ont montré qu'en supposant la conjecture des jeux uniques (en) (Unique Games Conjecture) cette approximation est optimale[6]. En supposant seulement que P est différent de NP, on obtient une limite à 16/17[7],[8].

Algorithmes pour des cas particuliers[modifier | modifier le code]

Pour les graphes planaires, le problème peut être résolu en temps polynomial[9], car il se réduit à un problème de couplage maximum lui-même polynomial (par exemple avec l'algorithme d'Edmonds (en)). C'est un résultat important pour les applications.

Dans le cas des graphes denses, on peut définir un PTAS[10].

Applications[modifier | modifier le code]

La coupe maximum est un objet assez naturel qui trouve des applications en physique statistique et en intégration à très grande échelle notamment[11].

Modèle d'Ising[modifier | modifier le code]

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 atomes a un spin, up ou down, et les interactions définissent alors des poids. Les coupes maximums correspondent alors aux états d'énergie minimale[12],[13].

Problème de Pinter[modifier | modifier le code]

Le problème de Pinter consiste à placer des fils des deux cotés d'une plaque, sans intersections, en minimisant le nombre fils traversant la plaque[14]. Ce problème peut lui aussi être décrit comme un problème de coupe maximum[15].

Bibliographie[modifier | modifier le code]

Ouvrages généraux[modifier | modifier le code]

  • (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,‎ 2003
  • (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 »
  • Richard M. Karp, « Reducibility among combinatorial problems », dans Complexity of Computer Computation, Plenum Press,‎ 1972, p. 85 -103
  • 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.
  • Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge,‎ 1995.

Articles sur le problème algorithmique[modifier | modifier le code]

  • (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)
  • (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, no 1,‎ 2007, p. 319 - 357 (DOI 10.1137/S0097539705447372)
  • (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,‎ 2000, p. 314-332

Sur les applications[modifier | modifier le code]

  • (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, no 3,‎ 1988, p. 493 - 513 (DOI 10.1287/opre.36.3.493, JSTOR 170992).
  • (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,‎ 1982, p. 673
  • Frédéric Meunier et Andras Sebo, « Parcours et coupes », dans Graphes et applications-vol. 2, JC Fournier,‎ 2007 (lire en ligne)
  • Ron Yair Pinter, « Optimal layer assignment for interconnect », Journal of VLSI and computer systems, Computer Science Press, vol. 1, no 2,‎ 1984, p. 123-137

Notes et références[modifier | modifier le code]

  1. (Garey Johnson NP)
  2. (Karp 1972)
  3. (Papadimitriou et Yannakakis 1991)
  4. (Gonzalez, Gaur et Krishnamurti 2007), section 4.10.1
  5. Voir (Goemans et Williamson 1995) pour l'article original et (Meunier et Sebo 2007) pour une explication en français.
  6. (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, no 1,‎ 2007, p. 319 - 357 (DOI 10.1137/S0097539705447372).
  7. (en) Johan Håstad, « Some optimal inapproximability results », Journal of the ACM, vol. 48,‎ 2001, p. 798–859 (DOI 10.1145/502090.502098)
  8. (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.
  9. (Hadlock 1975)
  10. Voir (Fernandez de la Vega et Karpinski 2000), notamment pour la définition précise de "dense".
  11. Voir (Barahona et al. 1988)
  12. Cette application est tirée de (Meunier et Sebo 2007), qui contient une explication plus complète.
  13. Cette application a été décrite pour la première fois dans (Barahona et al. 1982)
  14. Voir (Pinter 1984).
  15. Voir (Meunier et Sebo 2007). La dénomination "problème de Pinter", provient elle aussi de ce document.

Liens externes[modifier | modifier le code]