Complexidade dos endomorfismos dos contadores gráficos

Um homomorfismo de um gráfico $G = (V, E)$ para um gráfico é um mapeamento de para modo que se e são adjacentes em então e são adjacentes em . Um endomorfismo de um gráfico é um homomorfismo de para si mesmo; é livre de ponto fixo se não houver tal que seja $G' = (V', E')$ $f$ $V$ $V'$ $x$ $y$ $E$ $f(x)$ $f(y)$ $E'$ $G$ $G$ $x$ $f(x) = x$ não trivial se não for a identidade.

Recentemente, fiz uma pergunta relacionada a automorfismos poset (e gráficos) , isto é, endomorfismos bijetivos, cujo inverso também é um endomorfismo. Encontrei trabalhos relacionados a contar (e decidir a existência de) automorfismos, mas não foi possível encontrar nenhum resultado relacionado a endomorfismos.

Daí a minha pergunta: qual é a complexidade, dado um gráfico , de decidir a existência de um endomorfismo não trivial de ou de contar o número de endomorfismos? Mesma pergunta com endomorfismos sem ponto fixo. $G$ $G$

Penso que o argumento apresentado nesta resposta se estende a endomorfismos e justifica que o caso de gráficos bipartidos direcionados, ou posets, não é mais fácil do que o problema para gráficos gerais (o problema para gráficos gerais se reduz a esse caso), mas sua complexidade não parece simples de determinar. Sabe-se que decidir a existência de um homomorfismo de um gráfico para outro é difícil para NP (isso é claro, pois generaliza a coloração de gráficos), mas parece que restringir a pesquisa de homomorfismos de um gráfico para si mesmo pode facilitar o problema, portanto, isso não me ajuda a determinar a complexidade desses problemas.

cc.complexity-theory graph-algorithms counting-complexity graph-isomorphism homomorphism a3nm
fonte

A contagem de endomorfismos ou endomorfismos sem pontos fixos é completa para : dado um gráfico conectado , considere o gráfico que é a união disjunta de e um triângulo. Então $\mathsf{FP}^{\mathsf{\# P}}$ $G$ $G'$ $G$ $|\text{End}(G')| = (|\text{End}(G)| + \# 3COL(G))(\#\{\text{triangles in } G\} + 3^3)$ , para que o possa ser calculado usando duas contagens de endomorfismo (e, por um resultado geral, apenas um basta) e algum pós-processamento de politempo. Observe que o número de triângulos pode ser contado em tempo cúbico (ou mesmo multiplicação de matrizes). A mesma equação vale para os endomorfismos livres de ponto fixo, uma vez que as três cores e triângulos são endomorfismos livres de ponto fixo de . $\# 3COL$ $G'$

Se você deseja que seja conectado, faça o seguinte. Primeiro, observe que contar endomorfismos de gráficos coloridos em vértices (onde os vértices da cor só podem ser mapeados para outros vértices da cor ) é equivalente a contar os endomorfismos dos grafos, como a seguir. Deixe as cores ser . Para cada vértice da cor , adicione um novo ciclo ímpar separado de tamanho pelo menos ( $G'$ $c$ $c$ $\{1,...,C\}$ $v$ $c$ $C_v$ $n + 2c$ ) e conecte um vértice de a . Todo endomorfismo de corresponde a endomorfismos do novo gráfico (para cada ciclo, você tem duas opções de como mapeá-lo). Observe que nenhum vértice de pode mapear para vértices de qualquer , pois os ciclos são muito grandes (você precisaria ajustar um ciclo dentro de outro, o que não é possível para ciclos ímpares). $n=|V(G)|$ $C_v$ $v$ $G$ $2^n$ $G$ $C_v$

Agora, para criar uma versão do conectada, começamos com uma versão colorida e aplicamos a transformação acima. Comece como antes, adicionando a um triângulo separado . Agora adicione um único novo vértice que esteja conectado a todos os vértices em . Cor vermelho e todos os outros vértices azuis. $G'$ $G$ $\Delta$ $v_0$ $G \cup \Delta$ $v_0$

Joshua Grochow
fonte

Obrigado! Não tenho certeza da sua fórmula exata para

(Eu recebo

| E n d (G^{'}) |

$|\mathrm{End}(G')|$

(| E n d (G) | + # 3 C O L (G)) (# t r i a n g l e s + 3^{3})

$(|\mathrm{End}(G)| + \#3COL(G))(\#triangles + 3^3)$ , e algo semelhante para o ponto fixo-livre), mas o argumento ainda é válido. A segunda parte do seu argumento mostra dureza, mesmo assumindo conexão, acho que é verdade, mas acho que não se aplica diretamente a endomorfismos sem pontos fixos (existem pontos fixos nos mapeamentos de ciclo), mas isso não é tão importante. Eu ficaria mais curioso em saber: o problema de decisão é difícil para NP (para endomorfismos não triviais e sem pontos fixos)? Obrigado novamente!

a3nm 21/05

Você está certo sobre a fórmula - eu a atualizei. Para aplicar a segunda parte ao ponto fixo, coloque uma aresta de cada um dos dois vértices maximamente distantes de

. A contagem de pontos sem pontos fixos será um pouco diferente, mas acho que ainda funciona. (Você também pode precisar aumentar o tamanho dos ciclos ...). Para pares de gráficos rígidos (não há endos não triviais)

, decidir existência de endos de

(união disjuntos) é equivalente a decidir existência de um homomorphism

. Quase todos os gráficos são rígidos, por isso é bem possível que a decisão seja difícil para NP ...

C_{v}

$C_v$

v

$v$

G, H

$G,H$

G \cup H

$G \cup H$

G \to H

$G \to H$

H \to G

$H \to G$

Joshua Grochow

OK, acho que comprei o seu argumento para a contagem sem pontos fixos. Para decisão, na verdade, agora percebo que "O núcleo de um gráfico", Inferno, p. 8-9, parece provar que decidir a existência de um endomorfismo não trivial é NP completo. (A questão da endomorfismos-livre de ponto fixo permanece, mas há pouca razão para acreditar que não seria difícil também.)

a3nm

Complexidade dos endomorfismos dos contadores gráficos

Respostas: