Unvollständiger Subgraph-Isomorphismus

Betrachten Sie das folgende Problem: Wenn ein Abfragegraph und ein Referenzgraph , möchten wir die injektive Abbildung , die die Anzahl von minimiert Kanten so dass . Dies ist eine Verallgemeinerung des Subgraphen-Isomorphismus-Problems, bei dem wir zulassen, dass die Subgraphen bis zu einigen fehlenden Kanten isomorph sind und den Weg finden möchten, die Anzahl fehlender Kanten zu minimieren. $G = (V, E)$ $G' = (V', E')$ $f : V \rightarrow V'$ $(v_1, v_2) \in E$ $(f(v_1), f(v_2)) \notin E'$

Mich würde auch die gewichtete Version dieses Problems interessieren, bei der Vertexpaare ein Gewicht (das null sein muss, wenn und ebenso für , und wir wollen (das gibt es nur zu bestrafen Gewichte aus dem Abfrage-Diagramm größer als die des Referenz-Diagramms). $(v_1, v_2) \in V^2$ $w(v_1, v_2)$ $(v_1, v_2) \notin E)$ $G'$ $\sum_{v_1, v_2} (\max(0, w(v_1, v_2) - w(f(v_1), f(v_2))))$ $\max$

Meine Frage ist: Wurde dieses Problem bereits untersucht? Hat es einen bekannten Namen? Sind effiziente Approximationsalgorithmen bekannt?

Die Motivation für dieses Problem (abgesehen von der Tatsache, dass es sich um eine natürliche Verallgemeinerung des Subgraph-Isomorphismus-Problems handelt) ist, dass es eine gute Möglichkeit ist, einen Tischplan für eine Party zu erstellen: Das Abfrage-Diagramm ist das Diagramm der Gäste mit Kantengewichten Stellt das Ausmaß dar, in dem zwei Personen interagieren möchten, hat das Referenzdiagramm die Tischplätze als Eckpunkte und Kantengewichte, die angeben, inwieweit Kommunikation möglich ist, ist die Lösung des Problems eine Zuordnung von Personen zu Tischplätzen, die die soziale Struktur respektiert das größtmögliche Ausmaß.

cc.complexity-theory ds.algorithms graph-theory approximation-algorithms graph-isomorphism a3nm
quelle

Warum brauchen Sie "induziert" in den Titel?

Yota Otachi

@Yota Otachi: Weil ich es versaut habe. Vielen Dank!

23:38 Uhr

Antworten:

Ihr Problem ist das Maximum Common Edge Subgraph Problem (Max. CES), das wie folgt definiert ist: Finden Sie bei zwei Graphen und einen Graphen mit der maximalen Anzahl von Kanten, die zu einem Subgraphen von und zu einem Subgraphen von isomorph ist . $G$ $G'$ $H$ $G$ $G'$

Beweis : Sie finden einen Untergraphen von isomorph zu einem Untergraphen von , wobeiminimiert wird. Seitist eine Invariante von , wird genau dann minimiert, wennist maximiert. Offensichtlich ist isomorph zu einem Untergraphen von und zu einem Untergraphen von . QED $H$ $G$ $G'$ $|E_{G}| - |E_{H}|$ $|E_{G}|$ $G$ $|E_{G}| - |E_{H}|$ $|E_{H}|$ $H$ $G$ $G'$

Approximierbarkeit. In der Dissertation von Kann fand ich die Beschreibung "in einer Konstanten als nicht approximierbar bekannt" [3] (S. 115). In einem kürzlich erschienenen Aufsatz von Bahiense et al. [1] wird erwähnt, dass wennundmüssen nicht gleich sein, das Problem wird APX-schwer. Das Zitat für dieses Ergebnis ist jedoch eine unveröffentlichte private Mitteilung [2]. $|V_{G}|$ $|V_{G'}|$

L. Bahiense, G. Manic, B. Piva, CC de Souza. Das maximale Common-Edge-Subgraph-Problem: Eine polyedrische Untersuchung. Diskrete Angewandte Mathematik erscheint. doi: 10.1016 / j.dam.2012.01.026
MM Halldorsson, Persönliche Mitteilung, unveröffentlichtes Manuskript, 1994.
V. Kann. Zur Approximierbarkeit von NP-vollständigen Optimierungsproblemen. Ph.D. These, NADA-Bericht TRITA-NA-9206, 1992. http://www.nada.kth.se/~viggo/papers/phdthesis.pdf

Yota Otachi
quelle

Es sieht so aus, als ob dies in der Tat meinem Problem entspricht. Danke vielmals! Sind Ihnen die Ergebnisse einer gewichteten Version von Max CES bekannt?

a3nm

Ich habe keine Ahnung über die gewichtete Version. Ich denke, sollte , richtig?

max_{v_{1}, v_{2}} max (\dots)

$\max_{v_1,v_2} \max (\ldots)$

\sum_{v_{1}, v_{2}} max (\dots)

$\sum_{v_1,v_2} \max (\ldots)$

Yota Otachi

Ja, die Summe ist natürlicher, wenn wir den ungewichteten Fall verallgemeinern wollen, obwohl es meines Erachtens sinnvoll sein könnte, die Summe der Quadrate oder eine Funktion des Gewichtsunterschieds zu minimieren.

a3nm

Vielen Dank für die Bearbeitung. Ich stimme zu, es ist natürlich, die Summe der Gewichtsunterschiede (oder eine beliebige Funktion darauf) als Strafe zu verwenden.

Yota Otachi