Plus grand sous-graphe commun de deux graphes planaires maximaux

13

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 à GG1G2GG1G2G .

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?G1G2G1G1G2

Vinayak Pathak
la source
«L'isomorphisme des graphes sur deux graphes planaires maximaux est polynomial. Peut-être que cela aide en quelque sorte? " Il est au moins lié (vous le savez probablement déjà): l'existence d'un algorithme efficace pour décider de l'isomorphisme est certainement une condition nécessaire à l'existence d'un algorithme efficace pour trouver le plus grand sous-graphe commun.
Tsuyoshi Ito du
Oui bien sûr. Et ce n'est probablement pas suffisant. Je ne suis pas trop sûr, mais je pense qu'il existe des classes de graphes pour lesquelles l'isomorphisme est polynomial mais trouver le plus grand sous-graphe commun ne l'est pas?
Vinayak Pathak
Il semble que le problème soit complet. G pourrait être le plus grand cycle commun et on sait que le problème du cycle hamiltonien est N P- complet sur les graphes planaires maximaux. math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W82a/tech298.pdfNPGNP
Mohammad Al-Turkistany

Réponses:

5

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 .eeeM

Soit une instance dure construite de cette manière, et incorporez G de sorte que l'arête eGGe 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 GeGcHnG .

Notre exemple difficile pour le plus grand sous - graphe commun sera la paire 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)BHcHc ) seront suffisamment supérieurs à tous les autres sommets de H2cH , 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 HGeGc(n+2)c(n1)3cGc aux sommets mais moins que c ( -3cc(n1)H et a au moins c ( n + 2 ) arêtes est NP-complet.Bc(n+2)

David Eppstein
la source