Complexidade do homomorfismo do dígrafo para um ciclo orientado

Dado um grafo orientado fixo (dï¿½rafo) , a -COLORING problema decisão pergunta se um digrama de entrada tem um homomorphism para . (Um homomorfismo de para é um mapeamento de para que preserva os arcos, ou seja, se é um arco de , então é um arco de ) $D$ $D$ $G$ $D$ $G$ $D$ $f$ $V(G)$ $V(D)$ $uv$ $G$ $f(u)f(v)$ $D$

A classe de problemas COLORING está fortemente ligada à conjectura de dicotomia para CSPs declarada por Feder e Vardi (acessível no cidadão ). $D$

No presente artigo de 2001 (acessível na página do autor, aqui ), Feder prova um teorema dicotomia quando é um ciclo orientado (por ciclo orientada quero dizer um ciclo sem direção, onde cada aresta é substituído por um único arco, que pode ser orientado de forma arbitrária) , em outras palavras, ele mostra que para qualquer ciclo orientada , -COLORING é ou polinomial-tempo solúvel ou NP-completo. $D$ $D$ $D$

Infelizmente, a classificação de Feder é altamente não trivial e não explícita, pois a complexidade de muitos casos está relacionada à complexidade de certas variantes restritas de SAT que dependem da orientação. Ao examinar o artigo, não consegui determinar a resposta para minha pergunta:

Pergunta: Qual é o menor tamanho de um ciclo orientado modo que -COLORING seja NP-complete? $D$ $D$

A resposta pode ser declarada em algum lugar da literatura, mas não consegui encontrá-la.

Editar:Deixe-me dar mais detalhes sobre a classificação de Feder. Feder mostra que qualquer ciclo orientado a NP completo deve ser equilibrado, ou seja, ter o mesmo número de arcos nas duas direções (portanto, ele tem ordem uniforme). Em seguida, considere os "níveis" induzidos pela orientação (comece a percorrer o ciclo em um vértice arbitrário; se um arco der certo, você aumenta 1, se um arco fica à esquerda, diminui 1). Então, se houver no máximo uma "execução de cima para baixo", é polinomial. Se houver pelo menos três dessas "execuções" e o ciclo for um núcleo, será NP-completo. (No exemplo dos comentários de András, existem três "corridas", mas o ciclo não é essencial.) Os casos mais complicados são aqueles com duas "corridas de cima para baixo". Alguns são difíceis, outros polinomiais, e Feder os relaciona a problemas especiais de SAT para obter uma dicotomia.

Como uma pergunta intermediária: qual é o menor ciclo orientado que possui três execuções "de cima para baixo" e é um núcleo? Esse exemplo seria NP-completo pela discussão acima.

reference-request graph-theory np-hardness csp homomorphism Florent Foucaud
fonte

Não recordo uma resposta rápida na literatura (talvez Barnaby Martin ou Florent Madelaine saberiam). No entanto, o tamanho é de no máximo 6 vértices e 6 arestas direcionadas, pois é possível reduzir -Colouring a -Colouring para um dígrafo seis vértices substituindo cada aresta não direcionada nos gráficos por dois arcos apontando para um novo vértice entre seus pontos. pontos finais.

K_{3}

$K_3$

D

$D$

D

$D$

András Salamon

Obrigado András. No entanto, eu acho que a resposta deve ser maior porque o núcleo deste exemplo é simplesmente um dígrafo com um arco único, que pode ser resolvido em tempo polinomial ...

Florent Foucaud

Você está certo, a construção que propus é muito simples.

András Salamon

Perguntei a Florent Madelaine e Barnaby Martin, mas eles não sabem a resposta diretamente, embora pareçam estar interessados :-) Meu colega perguntou a Feder por e-mail na semana passada, mas ele ainda não respondeu.

Florent Foucaud

Meu segundo impulso foi usar uma versão rígida do triângulo. No entanto, com o dispositivo de rigidez de Chvátal et al. (JCT 1971) o triângulo rigidificado parece exigir um número de vértices que seja pelo menos 9v + 36, se o gráfico de entrada tiver v vértices e não estiver claro como modificar esses dispositivos para os caminhos. Talvez seja possível usar um caminho direcionado rígido para substituir cada aresta, mas não está claro para mim como fazer isso, mantendo a capacidade de mapear qualquer aresta do gráfico para qualquer aresta do triângulo (mas em nenhum outro lugar), pois o A maneira óbvia de fazer isso é exigir simetria.

András Salamon

Respostas:

Para a pergunta intermediária (um núcleo com três execuções de cima para baixo), que tal isso?

Alguma notação: descreverei execuções por palavras em , com, por exemplo, correspondendo a um subgrafo . O nível aumenta em arcos e diminui em arcos, e suponho que seu mínimo seja . Algumas restrições simples são: $\{l,r\}^*$ $llrl$ $\cdot\leftarrow\cdot\leftarrow\cdot\to\cdot\leftarrow\cdot$ $r$ $l$ $0$

Não pode haver uma execução consistindo apenas em s ou apenas em s, porque, caso contrário, há um homomorfismo óbvio de para essa execução (mapeando cada nó de para aquele com o mesmo nível). Isso também implica que o nível máximo deve ser pelo menos . $l$ $r$ $D$ $D$ $3$
Se o nível máximo fosse , todas as execuções top-bottom (resp bottom-top) teriam a forma (resp. ; novamente, não é muito difícil encontrar um homomorfismo de à execução, o que minimiza . $3$ $llr(lr)^ill$ $rrl(rl)^irr)$ $D$ $i$

No entanto, para o nível máximo existe uma solução de comprimento : considere dado por . Possui as execuções necessárias de cima para baixo e é um núcleo (veja abaixo). Pelas restrições acima, é necessariamente mínimo, pois cada execução possui apenas uma única borda "para trás". $4$ $36$ $D$ $(rrrlrrlllrll)^3$

Para nos convencer de que isso é essencial, vamos primeiro nomear os vértices ( ). Os vértices inferiores (ou seja, nível ) são . Qualquer homomorfismo de a um subgráfico deve preservar níveis e, em particular, ; módulo o óbvio automorfismo , basta considerar o caso . Considere a vizinhança de em (anotada com níveis): $v_1,\ldots,v_{36}$ $0$ $v_1,v_{13},v_{25}$ $\varphi$ $D$ $\varphi(v_1)\in\{v_1,v_{13},v_{25}\}$ $v_i\mapsto v_{i+12}$ $\varphi(v_1)=v_1$ $v_1$ $D$

$v_{34}(1)\to v_{35}(2)\leftarrow v_{36}(1)\leftarrow v_1(0)\to v_2(1)\to v_3(2)\to v_4(3)\leftarrow v_5(2)\to v_6(3)\to v_7(4)$

Começando com , temos . Mas se , então , e não temos valor possível para . Obtemos . Em seguida , mas para obtemos , sem valor possível para . Portanto, deve ser a identidade em toda a execução e, repetindo o mesmo argumento para as execuções restantes, o mesmo ocorre em todos os $\varphi(v_1)=v_1$ $\varphi(v_2)\in\{v_{36},v_2\}$ $\varphi(v_2)=v_{36}$ $\varphi(v_3)=v_{35}$ $\varphi(v_4)$ $\varphi(v_2)=v_2,\varphi(v_3)=v_3,\varphi(v_4)=v_4$ $\varphi(v_5)\in\{v_3,v_5\}$ $\varphi(v_5)=v_3$ $\varphi(v_6)=v_4$ $\varphi(v_7)$ $\varphi$ $v_1\to\ldots\to v_7$ $D$ . Em particular, não mapeia em um subgráfico apropriado. $\varphi$ $D$

Klaus Draeger
fonte

Essa mesma análise mostra que todos os ciclos orientados balanceados com duas execuções que são núcleos têm comprimento de pelo menos 24, certo? Então isso dá um limite mais baixo à resposta do problema principal.

David Eppstein

Sim, bom argumento.

Klaus Draeger

Ótimo, obrigado, isso é muito útil! Podemos nos convencer à mão de que isso é essencial? (observe que existe um algoritmo de tempo polinomial para verificar se um ciclo orientado é um núcleo: crie o conjunto de subcaminhos orientados modo que seja um arco de , e em seguida, verificar se mapeia para qualquer destes caminhos; isto pode ser feito em polytime, ver Gutjahr et al: sciencedirect.com/science/article/pii/0166218X9290294K )

D

$D$

| V (D) |

$|V(D)|$

{D - a

$\{D-a$

a

$a$

D}

$D\}$

D

$D$

Florent Foucaud

@FlorentFoucaud Adicionei um pouco mostrando que é um núcleo.

D

$D$

Klaus Draeger