Partout où j'ai lu sur le problème de coupe le plus clairsemé, il est seulement dit que le problème est connu pour être NP- dur. Où puis-je trouver une preuve de cela? Quel problème NP- dur connu se réduit au problème de coupe le plus clairsemé?
Je n'ai trouvé aucune preuve dans le livre de Vazirani - Approximation Algorithms, qui présente l'algorithme de Leighton Rao, ou le livre "Computers and Intractability" - qui résume de nombreux problèmes liés au NP . Je ne pouvais pas le trouver en recherchant (avec des chaînes de recherche évidentes) sur Google. Il y a un article de Chawla et al, qui suppose la conjecture UGC de Khot et prouve la dureté d'approximation de la coupe la plus clairsemée. J'espérais voir une preuve qui ne suppose aucune conjecture.
La preuve devrait simplement réduire un problème connu de NP- dur à la coupe la plus clairsemée.
Merci,
Arpita Korwar.
la source
Réponses:
[Déplacé du commentaire]
L'article " Les coupes les plus éparses et les goulots d'étranglement dans les graphiques " par David W. Matula, Farhad Shahrokhi donne une réduction du problème de coupe maximale. La preuve de dureté de Max-cut se trouve à Garey Johnson.
la source