Max-Cut APX est-il complet sur les graphiques sans triangle?

9

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

Standa Zivny
la source
Si vous ne trouvez pas de référence, et il semble que ce soit un argument original, alors envisagez de le poster ici: meta.cstheory.stackexchange.com/questions/784/…
Suresh Venkat

Réponses:

14

Oui, par une réduction de MaxCut à MaxCut sans triangle. Voici ce que Wikipedia appelle une réduction en L

GGGGG

Colin McQuillan
la source
9
Merci Colin! En cherchant une réponse, j'ai découvert la même astuce que vous appelez "3-stretch", également connue sous le nom de 2-subdivision. D'après ce que j'ai trouvé, il est probablement apparu pour la première fois dans cet article: Svatopluk Poljak: Une note sur les ensembles stables et la coloration des graphiques, Commentaire. Math. Univ. Carolinae 15 (1974) 307-309 (disponible ici: dml.cz/handle/10338.dmlcz/105554 )
Standa Zivny