Decydujący homomorfizm grafowy

Graf decydujący Homomorfizm jest ogólnie NP-Complete.

Czy istnieją wyniki, które badają ten problem, gdy leżące u podstaw wykresy mają strukturę algebraiczną (takie jak decydowanie o homomorfizmach z wykresów Coseleya lub Cayleya do innych wykresów o określonej strukturze również)? Oprócz wyników złożoności interesują mnie również pomocne techniki algebraiczne i / lub spektralne.

Jeśli jest klasą wykresów z ograniczoną szerokością, to problem homomorfizmu z wykresów w G można rozwiązać w czasie wielomianowym. Można to uogólnić na bardziej ogólną właściwość „wykresów, których rdzeń ograniczył szerokość”.$\mathcal{G}$$\mathcal{G}$

Grohe udowadnia odwrotnie: jeśli rdzenie wykresów w mają nieograniczoną szerokość, to problem homomorfizmu z G nie jest rozwiązany w czasie wielomianowym (przy założeniu F P T ≠ W [ 1 ] ). Dlatego jeśli ograniczysz wykres po lewej stronie do wykresów Cayleya itp., Ważne jest, czy rdzenie ograniczyły szerokość.$\mathcal{G}$$\mathcal{G}$$FPT\neq W[1]$

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

Zauważ, że to nie do końca odpowiada na twoje pytanie: w wyniku Grohe zakłada się, że wykres po prawej stronie jest dowolny. Wygląda na to, że interesują Cię wyniki, w których wykres po prawej stronie jest również ograniczony do określonej klasy grafów.

Decydowanie, czy istnieje homomorfizm grafowy, jest łatwiejsze niż liczenie liczby (ważonych) homomorfizmów grafowych.

Ważona skrzynka

$H$$G$$H$

Jin-Yi Cai, Xi Chen, Pinyan Lu. Wykres homomorfizmów ze złożonymi wartościami: twierdzenie o dychotomii .

$H$

$H$$H$

$q$$q$$q$

Nieważona obudowa

Nieważona obudowa jest znacznie prostsza. Poniżej stwierdzam Twierdzenie 1.1 z następującego artykułu.

Martin Dyer, Catherine Greehill. Złożoność liczenia homomorfizmów grafowych . (Również ten bezpośredni link do darmowego pliku PDF.)

Twierdzenie 1:

$H$$H$$H$