Dans le problème Max-Cut , on cherche un sous-ensemble S de sommets d'un graphe simple non orienté donné tel que le nombre d'arêtes entre S et le complément de S soit le plus grand possible.
Max-Cut est APX-complet sur les graphes à degrés bornés [PY91], et en fait APX-complet sur les graphes cubiques (ie graphes de degré 3) [AK00].
Max-Cut est NP-complet sur les graphiques sans triangle de degré au plus 3 [LY80] (sans triangle signifie que le graphique d'entrée ne contient pas K_3, le graphique complet sur 3 sommets, comme sous-graphique).
Question: Max-Cut APX est-il complet sur les graphiques sans triangle? (Remarque: degrés arbitraires autorisés)
Je vous remercie.
MISE À JOUR: Une réponse a été trouvée, mais je serais toujours intéressé par une référence pour ce résultat, s'il y en a.
Références:
[AK00] P. Alimonti et V. Kann: Quelques résultats d'exhaustivité APX pour les graphiques cubiques. Théor. Comput. Sci. 237 (1-2): 123-134, 2000. doi: 10.1016 / S0304-3975 (98) 00158-3
[LY80] JM Lewis et M. Yannakakis: Le problème de suppression de nœuds pour les propriétés héréditaires est NP-complet. J. Comput. Syst. Sci. 20 (2): 219-230, 1980. doi: 10.1016 / 0022-0000 (80) 90060-4
[PY91] CH Papadimitriou et M. Yannakakis: Optimization, Approximation, and Complexity Classes, J. Comput. System Sci., 43 (3): 425-440, 1991. doi: 10.1016 / 0022-0000 (91) 90023-X
Réponses:
Oui, par une réduction de MaxCut à MaxCut sans triangle. Voici ce que Wikipedia appelle une réduction en L
la source