Entscheidender Graphhomomorphismus

Die Entscheidung über den Homomorphismus des Graphen ist im Allgemeinen NP-vollständig.

Gibt es Ergebnisse, die dieses Problem untersuchen, wenn die zugrunde liegenden Graphen eine algebraische Struktur aufweisen (z. B. die Entscheidung über Homomorphismen von Cayley- oder Cayley-Coset-Graphen zu anderen Graphen mit einer bestimmten Struktur)? Neben Komplexitätsergebnissen interessieren mich auch hilfreiche algebraische und / oder spektrale Techniken.

Wenn eine Klasse von Graphen mit begrenzter Baumbreite ist, ist das Homomorphismusproblem aus Graphen in in Polynomzeit lösbar. Dies kann auf die allgemeinere Eigenschaft von "Graphen verallgemeinert werden, deren Kern die Baumbreite begrenzt hat".$\mathcal{G}$$\mathcal{G}$

Grohe beweist das Gegenteil: Wenn die Kerne der Graphen in eine unbegrenzte Baumbreite haben, ist das Homomorphismusproblem aus nicht polynomzeitlösbar (unter der Annahme von ). Wenn Sie also das Diagramm auf der linken Seite auf Cayley-Diagramme usw. beschränken, ist es wichtig, ob die Kerne die Baumbreite begrenzt haben.G F P T ≠ W [ 1 $\mathcal{G}$$\mathcal{G}$$FPT\neq W[1]$

http://dl.acm.org/authorize?951212

Beachten Sie, dass dies Ihre Frage nicht vollständig beantwortet: Im Ergebnis von Grohe wird angenommen, dass das Diagramm auf der rechten Seite willkürlich ist. Sie scheinen an Ergebnissen interessiert zu sein, bei denen das Diagramm auf der rechten Seite auch auf eine bestimmte Klasse von Diagrammen beschränkt ist.

Die Entscheidung, ob ein Graphhomomorphismus vorliegt, ist einfacher als die Anzahl der (gewichteten) Graphhomomorphismen zu zählen.

Gewichteter Fall

Für ungerichtete Zieldiagramme (dh die Anzahl der gewichteten Diagrammhomomorphismen von einem Eingabegraphen G nach H ) gibt es einen Dichotomiesatz.$H$$G$$H$

Jin-Yi Cai, Xi Chen und Pinyan Lu. Graph Homomorphismen mit komplexen Werten: Ein Dichotomie-Theorem .

$H$

$H$$H$

$q$$q$$q$

Ungewichteter Fall

Der ungewichtete Fall ist viel einfacher. Im Folgenden stelle ich Satz 1.1 aus dem folgenden Artikel fest.

Martin Dyer, Catherine Greehill. Die Komplexität der Zählung von Graphhomomorphismen . (Auch dieser direkte Link zu einem kostenlosen PDF.)

Satz 1:

$H$$H$$H$