Dans un graphe G=(V,E) simple non orienté, un stable (resp. co-2-plexe) est un ensemble de sommets dont le sous-graphe induit contient seulement des sommets de degré au plus 0 (resp. 1). Une clique (resp. 2-plexe) est un ensemble de sommets induisant un sous-graphe dont le complémentaire est un stable (resp. co-2-plexe). Trouver un co-2-plexe de poids maximal est un problème NP-difficile qui se rencontre dans la littérature pour l'analyse de communautés dans les réseaux sociaux. Pour résoudre certaines instances il est nécessaire de décomposer le problème en trouvant pour chaque sommet le co-2-plexe de poids maximal le contenant; ce qui revient à résoudre |V| fois le problème sur différents sous-graphes induits. De manière analogue à la formulation PLNE par les contraintes de cliques pour le problème de stable de poids maximum, une formulation PLNE par les contraintes de 2-plexes existe pour le problème de co-2-plexe de poids maximum. McClosky et Hicks ont prouvé que la relaxation linéaire de cette formulation est entière seulement pour les 2-plexes, chemins, trous de taille multiple de 3, ainsi que les co-2-plexes.

Nous introduisons le total augmented graph de G, noté
T(G), dans lequel l'ensemble des stables est en bijection avec l'ensemble des co-2-plexes de G. Cette bijection nous permet d'obtenir des résultats sur le problème du co-2-plexe de poids maximal à partir de résultats connus pour le problème du stable de poids maximal. En particulier, nous montrons que le problème de co-2-plexe de poids maximal est polynomial dans une classe de graphes contenant les graphes cordaux et inclue dans les graphes parfaits. Nous obtenons également une formulation, étendue et compacte pour le polytope des co-2-plexes d'un graphe cordal.