Decidindo homomorfismo gráfico

Decidindo o gráfico O homomorfismo é geralmente NP-Completo.

Existem resultados que estudam esse problema quando os gráficos subjacentes têm estrutura algébrica (como decidir homomorfismos dos gráficos de cosset de Cayley ou Cayley para outros gráficos com alguma estrutura definida também)? Além disso, resultados de complexidade também estão interessados ​​em técnicas algébricas e / ou espectrais úteis.

Se é uma classe de gráficos com largura de árvore limitada, o problema de homomorfismo dos gráficos em G é solucionável em tempo polinomial. Isso pode ser generalizado para a propriedade mais geral de "gráficos cujo núcleo limitou a largura da árvore".$\mathcal{G}$$\mathcal{G}$

Grohe prova o contrário: se os núcleos dos gráficos em têm largura de árvore ilimitada, então o problema de homomorfismo de G não é passível de solução polinomial no tempo (assumindo F P T ≠ W [ 1 ] ). Portanto, se você restringir o gráfico do lado esquerdo aos gráficos de Cayley, etc., o que importa é se os núcleos limitaram a largura da árvore.$\mathcal{G}$$\mathcal{G}$$FPT\neq W[1]$

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

Observe que isso não responde completamente à sua pergunta: no resultado de Grohe, supõe-se que o gráfico do lado direito seja arbitrário. Você parece estar interessado em resultados nos quais o gráfico do lado direito também está restrito a alguma classe específica de gráficos.

Decidir se existe um homomorfismo gráfico é mais fácil do que contar o número de homomorfismos gráficos (ponderados).

Caso ponderado

Para os gráficos alvo não direcionados (ou seja, o número de homomorfismos dos gráficos ponderados de um gráfico de entrada G a H ), existe um teorema da dicotomia.$H$$G$$H$

Jin-Yi Cai, Xi Chen, Pinyan Lu. Homomorfismos de gráfico com valores complexos: um teorema da dicotomia .

$H$

É um pouco difícil explicar quais gráficos $H$$H$

A rastreabilidade resulta da capacidade de calcular com eficiência a soma exponencial em uma sequência de variáveis ​​módulo que formam um polinômio quadrático no expoente de uma $q$$q$$q$

Caso não ponderado

O caso não ponderado é muito mais simples. Abaixo, afirmo o Teorema 1.1 do artigo a seguir.

Martin Dyer, Catherine Greehill. A complexidade da contagem de homomorfismos gráficos . (Também este link direto para um PDF gratuito.)

Teorema 1:

Seja um gráfico fixo. Então, o problema de contar as cores H dos gráficos é # P-complete se H tiver um componente conectado que não seja um gráfico completo com todos os loops presentes ou um gráfico bipartido completo sem loops presentes. Caso contrário, o problema de contagem está em P.$H$$H$$H$