Maior subgrafo comum de dois gráficos planares máximos

Considere o seguinte problema -

Dado máxima planar gráficos e L 2 , encontrar o gráfico G com o número máximo de arestas de modo a que haja um subgráfico (induzida não necessariamente) em ambos G 1 e G 2 que é isomorfa a L .$G_1$$G_2$$G$$G_1$$G_2$$G$

Isso pode ser feito em tempo polinomial? Se sim, então como?

Sabe-se que se e G 2 são gráficos gerais, o problema é NP-completo (porque G 1 pode ser um clique). Também se sabe que se G 1 e G 2 são árvores ou k-árvores parciais de grau limitado, então o problema pode ser resolvido em tempo polinomial. E o caso planar máximo? Alguém sabe disso? O isomorfismo do gráfico em dois gráficos planares máximos é polinomial. Talvez isso ajude de alguma forma?$G_1$$G_2$$G_1$$G_1$$G_2$

É NP-completo, através de uma versão modificada da redução que Wigderson usou para provar que a Hamiltonicidade dos gráficos planares máximos é NP-completa.

Um exame cuidadoso da prova de dureza de Wigderson em 1982 para ciclos hamiltonianos em gráficos planares máximos ( http://www.math.ias.edu/avi/node/820 ) mostra que as instâncias produzidas por sua redução têm a propriedade de que existem existe uma aresta tal que existe um ciclo hamiltoniano através de e ou não existe um ciclo hamiltoniano. Por exemplo, e pode ser escolhido como uma das arestas em um dos gadgets M de Wigderson .$e$$e$$e$$M$

Seja uma instância difícil construída dessa maneira e incorpore G de modo que a aresta e pertença ao triângulo externo da incorporação. Conectar muitas cópias deste gráfico incorporado de modo a que as suas e -edges formar um ciclo, e fazer o resultado máximo planar de novo pela adição de mais dois vértices, um em cada lado deste ciclo, ligados a todos os vértices expostas das cópias de L . Deixe o número de cópias seja C , e chamar o gráfico resultante H . Deixe que n seja o número de vértices em L .$G$$G$$e$$e$$G$$c$$H$$n$$G$

O nosso exemplo duro para a maior subgráfico comum será o par , onde B é uma bipirâmide com o mesmo número de vértices como H . Assim, um subgrafo comum ótimo terá que emparelhar todos os vértices. Se fizermos c grande o suficiente, o subgrafo necessariamente emparelhará os vértices da bipirâmide com os dois vértices adicionados em H , porque seus graus ( c e 2 c ) serão suficientemente mais altos que todos os outros vértices em H , de modo que a adição desses graus para o tamanho da solução compensará qualquer interrupção causada por esse pareamento em outro lugar.$(H,B)$$B$$H$$c$$H$$c$$2c$$H$

Se é hamiltoniano, o subgrafo comum formado pela correspondência do ciclo hamiltoniano (menos e ) nas cópias de G ao equador da bipiramide terá c ( n + 2 ) arestas, c ( n - 1 ) para o equador e 3 c para os ápices. Se G não for hamiltoniano, (para opções suficientemente grandes de c para que a solução ótima emparelhe os vértices corretamente) qualquer subgrafo comum terá menos arestas: ainda 3 c nos vértices, mas menos que c ( $G$$e$$G$$c(n+2)$$c(n-1)$$3c$$G$$c$$3c$ outro lugar. Portanto, testar se o subgrafo comum de H e B possui pelo menos c ( n + 2 ) arestas é NP-completo.$c(n-1)$$H$$B$$c(n+2)$