Größter gemeinsamer Teilgraph zweier maximal planarer Graphen

Betrachten Sie das folgende Problem -

Bestimmen Sie für die maximalen ebenen Graphen und G 2 den Graphen mit der maximalen Anzahl von Kanten, sodass sowohl in als auch in ein (nicht notwendigerweise induzierter) Teilgraph vorhanden ist, der zu isomorph ist .$G_1$$G_2$G 1 G 2$G$$G_1$$G_2$$G$

Kann dies in polynomialer Zeit erfolgen? Wenn ja, wie?

Es ist bekannt, dass, wenn und allgemeine Graphen sind, das Problem NP-vollständig ist (weil eine Clique sein könnte). Es ist auch bekannt, dass, wenn und Bäume oder teilweise k-Bäume mit begrenztem Grad sind, das Problem in Polynomzeit gelöst werden kann. Was ist also mit dem maximalen planaren Fall? Weiß jemand das? Der Graphisomorphismus auf zwei maximalen ebenen Graphen ist polynomial. Vielleicht hilft das irgendwie?G 2 G 1 G 1 G $G_1$$G_2$$G_1$$G_1$$G_2$

Es ist NP-vollständig, über eine modifizierte Version der Reduktion, die Wigderson verwendet hat, um zu beweisen, dass die Hamiltonizität maximaler planarer Graphen NP-vollständig ist.

Eine sorgfältige Untersuchung von Wigdersons 1982er NP-Vollständigkeitsnachweis der Härte für Hamilton-Zyklen in maximal planaren Graphen ( http://www.math.ias.edu/avi/node/820 ) zeigt, dass die durch seine Reduktion erzeugten Instanzen die Eigenschaft haben, dass sie dort vorliegen existiert eine Kante so dass entweder ein Hamilton-Zyklus durch e existiert oder überhaupt kein Hamilton-Zyklus existiert. Zum Beispiel kann e als eine der Kanten in einem von Wigdersons M- Gadgets gewählt werden.$e$$e$$e$$M$

Sei eine auf diese Weise konstruierte harte Instanz und bette G so ein, dass die Kante e zum äußeren Dreieck der Einbettung gehört. Verbinden Sie viele Kopien dieses eingebetteten Graphen so, dass ihre E- Kanten einen Zyklus bilden, und machen Sie das Ergebnis wieder maximal planar, indem Sie zwei weitere Scheitelpunkte auf jeder Seite dieses Zyklus hinzufügen, die mit allen exponierten Scheitelpunkten der Kopien von G verbunden sind . Lassen Sie die Anzahl der Kopien sein c , und rufen Sie die resultierende Graph H . Lassen Sie n die Anzahl der Ecken in seiner G .$G$$G$$e$$e$$G$$c$$H$$n$$G$

Unsere harte Instanz für den größten gemeinsamen Teilgraphen ist das Paar wobei B eine Bipyramide mit der gleichen Anzahl von Eckpunkten wie H ist . Somit muss ein optimaler gemeinsamer Untergraph alle Eckpunkte koppeln. Wenn wir c groß genug machen, werden die Scheitelpunkte der Bipyramide notwendigerweise mit den beiden hinzugefügten Scheitelpunkten in H gepaart , da ihre Grade ( c und 2 c ) ausreichend höher sind als jeder andere Scheitelpunkt in H , so dass diese Grade addiert werden Die Änderung der Lösungsgröße gleicht Störungen an anderer Stelle aus, die durch dieses Pairing verursacht wurden.$(H,B)$$B$$H$$c$$H$$c$$2c$$H$

Wenn Hamilton ist, hat der gemeinsame Teilgraph, der durch Anpassen des Hamilton-Zyklus (minus e ) in den Kopien von G an den Äquator der Bipyramide gebildet wird, c ( n + 2 ) Kanten, c ( n - 1 ) für den Äquator und 3 c für die Spitzen. Wenn G nicht Hamilton ist, hat (für eine ausreichend große Auswahl von c, dass die optimale Lösung die Scheitelpunkte korrekt paart) jeder gemeinsame Teilgraph weniger Kanten: immer noch 3 c an den Scheitelpunkten, aber weniger als c ( $G$$e$$G$$c(n+2)$$c(n-1)$$3c$$G$$c$$3c$ anderswo. Die Prüfung, ob der gemeinsame Teilgraph von H und B mindestens c ( n + 2 ) Kanten hat, ist NP-vollständig.$c(n-1)$$H$$B$$c(n+2)$