Plus grand sous-graphe commun de deux graphes planaires maximaux

Considérez le problème suivant -

Étant donné les graphes planaires maximaux et G 2 , trouvez le graphique G avec un nombre maximal d'arêtes tel qu'il y ait un sous-graphe (pas nécessairement induit) dans G 1 et G 2 qui est isomorphe à $G_1$$G_2$$G$$G_1$$G_2$$G$ .

Peut-on le faire en temps polynomial? Si oui, alors comment?

On sait que si et G 2 sont des graphiques généraux, alors le problème est NP-complet (car G 1 pourrait être une clique). On sait également que si G 1 et G 2 sont des arbres ou des k-arbres partiels à degrés bornés, le problème peut être résolu en temps polynomial. Et le cas planaire maximal? Quelqu'un le sait-il? L'isomorphisme des graphes sur deux graphes planaires maximaux est polynomial. Peut-être que cela aide en quelque sorte?$G_1$$G_2$$G_1$$G_1$$G_2$

Il est NP-complet, via une version modifiée de la réduction que Wigderson a utilisée pour prouver que l'hamiltonicité des graphes planaires maximaux est NP-complète.

Un examen attentif de la preuve de dureté NP-complétude de 1982 de Wigderson pour les cycles hamiltoniens dans les graphes planaires maximaux ( http://www.math.ias.edu/avi/node/820 ) montre que les instances produites par sa réduction ont la propriété qu'il y existe un bord tel qu'il existe un cycle hamiltonien passant par e ou qu'il n'y ait aucun cycle hamiltonien du tout. Par exemple, e peut être choisi pour être l'un des bords de l'un des M- gadgets de Wigderson .$e$$e$$e$$M$

Soit une instance dure construite de cette manière, et incorporez G de sorte que l'arête $G$$G$$e$ appartient au triangle extérieur de l'incorporation. Connectez plusieurs copies de ce graphique intégré afin que leurs -edges forment un cycle, et de faire à nouveau le résultat maximal plan en ajoutant deux sommets, un de chaque côté de ce cycle, relié à tous les sommets exposés des copies de G . Que le nombre de copies soit c , et appeler le graphe résultant H . Soit n le nombre de sommets de $e$$G$$c$$H$$n$$G$ .

Notre exemple difficile pour le plus grand sous - graphe commun sera la paire où B est un bipyramide avec le même nombre de sommets que H . Ainsi, un sous-graphe commun optimal devra coupler tous les sommets. Si nous faisons c assez grand, le sous-graphe appairera nécessairement les sommets de la bipyramide avec les deux sommets ajoutés en H , car leurs degrés ( c et$(H,B)$$B$$H$$c$$H$$c$ ) seront suffisamment supérieurs à tous les autres sommets de$2c$$H$ , de sorte que l'addition de ces degrés à la taille de la solution compensera toute perturbation causée ailleurs par cet appariement.

Si est hamiltonien, le sous-graphe commun formé en faisant correspondre le cycle hamiltonien (moins e ) dans les copies de G à l'équateur de la bipyramide aura c ( n + 2 ) arêtes, c ( n - 1 ) pour l'équateur et 3 c pour les sommets. Si G n'est pas hamiltonien, alors (pour des choix de c suffisamment grands pour que la solution optimale associe correctement les sommets), tout sous-graphe commun aura moins de bords: toujours 1 ) ailleurs. Donc, tester si le sous-graphique commun de $G$$e$$G$$c(n+2)$$c(n-1)$$3c$$G$$c$ aux sommets mais moins que c ( $3c$$c(n-1)$$H$ et a au moins c ( n + 2 ) arêtes est NP-complet.$B$$c(n+2)$