Graph Isomorphism Problem

[Baalzamon]

Hallo,

Ich habe das Problem, das ich herausfinden möchte, ob ein Graph G1 ein Teilgraph von einem anderen Graphen G2 ist. 'Pattern Matching für Graphen' beschreibt mein Problem eigentlich sehr gut. ;)

Ich habe mal ein bisschen gegoogelt und denke, dass das Graph Isomorphism Problem für planare Graphen schon so ziemlich genau das Problem ist und offensichtlich kann man das in polynomieller Zeit lösen.

Leider habe ich irgendwie keine vernünftige Erklärung, Namen oder Entdecker für den verwendeten Algorithmus gefunden.

Kann mir da jemand auf die Sprünge helfen? Vielleicht bin ich einfach nur zu blöd zum googlen, oder ich bin einfach blind wenn es darum geht die richtigen Links zu sehen.

Ich benutze die Boost Graph-Library um meinen Graphen abzubilden. Wenn es dafür (was mir nicht unwahrscheinlich erscheint) bereits einen fertigen Algorithmus als Open-Source gibt, so nehme ich den auch gerne. Ich muss das Rad nicht neu erfinden.

[Aquaschaf]

Graph isomorphism ist die Frage ob zwei Graphen bis auf die Benennung der Knoten und Kanten gleich sind. Was du hast ist das subgraph isomorphism problem. Und das ist auch für planare Graphen NP-vollständig. Siehe auch: http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

[Baalzamon]

Hmmm...


When G is a planar graph and H is fixed, the running time of subgraph isomorphism can be reduced to linear time.


So einen Fall habe ich. Ich habe ein gegebenes 'Muster' und möchte wissen ob es in einem größeren planaren Graphen vorkommt.

[Actionhank]

Hmmm...



So einen Fall habe ich. Ich habe ein gegebenes 'Muster' und möchte wissen ob es in einem größeren planaren Graphen vorkommt.

Kann mir eigentlich auch nicht vorstellen, dass das für planare Graphen nicht NP-vollständig sein sollte.
Siehe Wikilink und Quelle [2].

[Baalzamon]

Hmmm...

Ich könnte für mein Problem auch den 'Zielgraphen' in seine Zusammenhangskomponenten zerlegen und jede Komponente gegen das Muster vergleichen. Damit hätte ich den Spezialfall des Graph Isomorphismus.

[Aquaschaf]

Hmmm...

So einen Fall habe ich. Ich habe ein gegebenes 'Muster' und möchte wissen ob es in einem größeren planaren Graphen vorkommt.

Das habe ich übersehen :) Aber jetzt hast du immerhin eine Quelle und den Algorithmus (http://www.cs.brown.edu/sites/jgaa/accepted/99/Eppstein99.3.3.pdf).

[Baalzamon]

Danke für das Paper. :)

Tante Edith meint... Uff... 27 Seiten. Na gut.

[Baalzamon]

Boost kommt übrigens auch mit einem Isomorphismus Algorithmus (http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/isomorphism.html).

Um mir selbst arbeit zu ersparen werde ich vielleicht tatsächlich einfach meinen Grpahen in die einzelenen Zusammenhangskomponenten zerlegen (auch das ist bereits in Boost implementiert), eine Vorauswahl treffen (zum Beispiel Komponenten mit nur einem Knoten rauswerfen) und dann jede Komponente auf Isomorphismus zu jedem Muster testen was ich habe.

Dauert mit Sicherheit länger (Laufzeit O(|V|!) ... <gulp>), aber ich habe gerade echt wenig Lust den ganzen Scheiss selber neu zu implementieren.