Isomorphisme sous-graphique imparfait

Considérons le problème suivant: étant donné un graphe de requête et un graphe de référence G ′ = ( V ′ , E ′ ) , nous voulons trouver la cartographie injective f : V → V ′ qui minimise le nombre d'arêtes ( v 1 , v 2 ) ∈ E tel que ( f ( v 1 ) , f ( v 2 ) $G = (V, E)$$G' = (V', E')$$f : V \rightarrow V'$$(v_1, v_2) \in E$ . Il s'agit d'une généralisation duproblème d'isomorphisme des sous-graphesoù nous permettons aux sous-graphes d'être isomorphes jusqu'à quelques arêtes manquantes et voulons trouver le moyen de minimiser le nombre d'arêtes manquantes.$(f(v_1), f(v_2)) \notin E'$

Je serais également intéressé par la version pondérée de ce problème, où les couples de sommets portent un poids w ( v 1 , v 2 ) (qui doit être nul si ( v 1 , v 2 ) ∉ E ) , ainsi que pour G ′ , et nous souhaitons minimiser ∑ v 1 , v 2 ( max ( 0 , w ( $(v_1, v_2) \in V^2$$w(v_1, v_2)$$(v_1, v_2) \notin E)$$G'$ (le maximum est là pour ne pénaliser que les poids du graphique de requête étant plus grands que ceux du graphique de référence).$\sum_{v_1, v_2} (\max(0, w(v_1, v_2) - w(f(v_1), f(v_2))))$$\max$

Ma question est: ce problème a-t-il déjà été étudié? At-il un nom bien connu? Existe-t-il des algorithmes d'approximation efficaces connus?

La motivation de ce problème (en dehors du fait qu'il semble être une généralisation naturelle du problème d'isomorphisme du sous-graphique) est qu'il s'agit d'une bonne façon de faire un plan de table pour une fête: le graphique de requête est le graphique des invités avec des poids de bord représentant la mesure dans laquelle deux personnes veulent interagir, le graphique de référence a les sièges de table en tant que sommets et poids de bord indiquant dans quelle mesure la communication est possible, la solution du problème est une cartographie des personnes aux sièges de table qui respecte la structure sociale à dans toute la mesure du possible.

Votre problème est le problème de sous-graphe maximum commun (Max CES) défini comme suit: étant donné deux graphiques et G ′ , trouvez un graphique H avec le nombre maximal de bords isomorphes à un sous-graphique de G et à un sous-graphique de G ′ .$G$$G'$$H$$G$$G'$

Preuve : vous trouvez un sous-graphe de G isomorphe à un sous-graphe de G ′ , où | E G | - | E H | est minimisé. Depuis | E G | est un invariant de G , | E G | - | E H | est minimisé si et seulement si | E H | est maximisé. Clairement, H est isomorphe à un sous-graphique de G et à un sous-graphique de $H$$G$$G'$$|E_{G}| - |E_{H}|$$|E_{G}|$$G$$|E_{G}| - |E_{H}|$$|E_{H}|$$H$$G$ . QED$G'$

Approximabilité. Dans la thèse de doctorat de Kann, j'ai trouvé la description «inconnue pour être approximable dans une constante» [3] (p. 115). Dans un article récent de Bahiense et al. [1], il est mentionné que si et | V G ′ | ne sont pas tenus d'être égaux, le problème devient dur APX. Mais la citation de ce résultat est une communication privée non publiée [2].$|V_{G}|$$|V_{G'}|$

1. L. Bahiense, G. Manic, B. Piva, CC de Souza. Le problème du sous-graphique de bord commun maximal: une enquête polyédrique. Discrete Applied Mathematics, à paraître. doi: 10.1016 / j.dam.2012.01.026
2. MM Halldorsson, Communication personnelle, manuscrit non publié, 1994.
3. V. Kann. Sur l'approximation des problèmes d'optimisation NP-complete. doctorat Thèse, rapport NADA TRITA-NA-9206, 1992. http://www.nada.kth.se/~viggo/papers/phdthesis.pdf