Ein Teil der Schwierigkeit, mehr über dieses Problem herauszufinden, besteht darin, dass sich das Graph-Matching-Problem von seinem viel bekannteren Cousin, dem Matching-Problem, unterscheidet, aber bei der Verwendung von Suchmaschinen schwer zu unterscheiden ist.
Gegeben sind zwei Graphen und so dass besteht die Aufgabe darin, eine Bijektion zu finden , so dass diese Bijektion so viele Entsprechungen zwischen den Kanten von und wie möglich herstellt.
Mit anderen Worten, wenn und die Adjazenzmatrizen sind, dann wollen wir maximieren
Dieses Problem enthält eindeutig den Graphisomorphismus als Sonderfall und kann unter einer (nicht-polynomialen!) Reduktion auf eine zweiteilige Anpassung reduziert werden.
Welche Art von Algorithmen gibt es und was ist über ihre Komplexität bekannt?
Das Papier, auf das @Austin Buchanan oben über den ungefähren Graph-Isomorphismus hingewiesen hat, scheint nicht der angeforderten Version zu entsprechen. Ich gehe davon aus, dass die Adjazenzmatrix Einträge enthält. In diesem Fall misst das Objektiv nur die übereinstimmenden Kanten. Das ungefähre Graph-Isomorphismus-Modell misst sowohl die übereinstimmenden als auch die nicht übereinstimmenden Kanten, was es aus approximativer Sicht etwas einfacher macht.0,1
Es scheint, dass das gestellte Problem mindestens genauso schwer ist wie das Dichte-Subgraph-Problem, das derzeit nur eine Polynomnäherung zulässt. Weitere Informationen und den aktuellen Status in Bezug auf Algorithmen und Härte finden Sie unter http://arxiv.org/abs/1001.2891 und http://arxiv.org/abs/1110.1360 .k
Nun zur Reduzierung. Angenommen, wir wollen das Dichte-Subgraph-Problem in einem Graphen lösen . das heißt, wir wollen eine Teilmenge von Knoten , die die Anzahl der Kanten im induzierten Graphen maximiert . Sie können dies auf Ihr Problem reduzieren, indem Sie als einen Graphen festlegen , der aus einer Clique auf Vertices und isolierten Vertices besteht, und wird auf .k H k S G[S] G k n−k G′ H
quelle