Une variante du problème du dominant

Euler_du_reWeil

Bonjour à tous, 

Pour un premier post dans la section Informatique théorique, je souhaiterais partager une version alternative du problème du dominant qui me semble suffisamment intéressante pour la porter à l'attention du forum. 

La formulation en est très simple : Étant donné un graphe $G=(V,E)$, on cherche à trouver deux sous-ensembles dominants $V_1$ et $V_2$ tels que $|V_1|+|V_2|+|V_1 \cap V_2|$ soit minimal. 

N'étant pas coutumier du fait d'étudier des problèmes d'algorithmique (ou du moins ayant laissé avec nostalgie cette discipline à mes années de classes préparatoires), je n'ai pas réussi à trouver de littérature concernant ce problème dans le cas général ie sans hypothèses sur le type de graphe étudié. Peut-être ce problème dispose-t-il d'une dénomination consacrée, mais je l'ignore...

Travaillant avec des graphes de taille conséquente, la NP complétude du problème anéantit tout espoir d'avoir une solution exacte. Toutefois, je serais très intéressé par toute référence ou approche heuristique permettant d'obtenir des bonnes approximations d'une solution. 

Merci d'avance de votre lecture et futures réponses, vous souhaitant une excellente journée. 

Math Coss

Pour les béotiens comme moi, un ensemble dominant d'un graphe $G = (S, A)$ est un sous-ensemble $D$ de l'ensemble $S$ des sommets tel que tout sommet qui n'appartient pas à $D$ possède au moins une arête d'extrémité un sommet de $D$.