Alguém encontrou algoritmo polinomial no isomorfismo do ciclo hamiltoniano?

Como o título diz, alguém encontrou um algoritmo de tempo polinomial para verificar se dois gráficos com ciclo hamiltoniano são isomórficos? Esse problema está completo?

complexity-theory graph-theory time-complexity Leo Sanchez
fonte

Definitivamente não, para gráficos direcionados pelo menos. Porque o melhor algoritmo para isomorfismo de torneio leva

O (n^{\log n})

$O(n^{\log{n}})$ . E Torneios são os gráficos com caminhos Hamiltonianos. Consulte uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/…

rizwanhudda

@rizwanhudda Muito obrigado. Posso lhe fazer mais uma pergunta? Esse problema está completo?

Leo Sanchez

Além disso, e os ciclos?

Leo Sanchez

Não conheço nenhum resultado sobre o ciclo hamiltoniano. Mas, esse problema não pode ser NP-Complete, pois é um caso especial de isomorfismo de gráfico. E o isomorfismo do gráfico não é conhecido como NP-Complete.

rizwanhudda

Como rizwanhudda disse, esse problema é um caso especial do problema de isomorfismo gráfico e, portanto, não é conhecido por ser NP completo. Não podemos dizer que "esse problema não pode ser NP-completo" por causa disso, porque o problema do isomorfismo gráfico pode ser NP-completo. No entanto, muitos teóricos da complexidade acreditam que o problema do isomorfismo gráfico não é NP completo (e, portanto, eles também acreditam que seu problema não é NP completo) porque a completude NP do problema isomorfismo gráfico contradiz a conjectura chamada “o hierarquia polinomial não entra em colapso. "

Tsuyoshi Ito

Respostas:

O que se segue é retirado do comentário de Tsuyoshi Ito .

Como rizwanhudda disse , esse problema é um caso especial do problema de isomorfismo gráfico e, portanto, não é conhecido por ser NP completo. Não podemos dizer que "esse problema não pode ser NP-completo" por causa disso, porque o problema do isomorfismo gráfico pode ser NP-completo. No entanto, muitos teóricos da complexidade acreditam que o problema do isomorfismo gráfico não é NP completo (e, portanto, eles também acreditam que seu problema não é NP completo) porque a completude NP do problema isomorfismo gráfico contradiz a conjectura chamada “o hierarquia polinomial não entra em colapso. "

Raphael
fonte

Por favor, não se sinta obrigado a marcar uma resposta como wiki da comunidade apenas porque é uma cópia do meu comentário, caso você ou qualquer outra pessoa sinta isso.

Tsuyoshi Ito

Bem, acho que essa resposta deve ser atualizada agora que o IG é conhecido por ser quase polinomial.

Guillermo Angeris

Como sugerido por Kaveh, talvez essa seja uma redução que possa provar que a classe de gráficos com um ciclo hamiltoniano é GI completa.

Dados dois gráficos $G_1 = (V_1,E_1)$ e $G_2 = (V_2,E_2)$ , $|V_1| = |V_2|=n$ , expandir $G_1$ com um gráfico completo $K_{2n}$ rotular seus nós em pares $(a_i, b_i)$ ; então para cada vértice $u_i \in |V_1|$ adicione duas arestas $(a_i,u_i)$ e $(u_i,b_i)$ que conectam $G_1$ ao $K_{2n}$ . Expandir $G_2$ do mesmo jeito.

Por construção, os dois gráficos expandidos $G'_1$ e $G'_2$ tem um ciclo hamiltoniano $(a_1 u_1 b_1 a_2 u_2 b_2 ... a_n u_n b_n a_1)$ e os gráficos originais são isomórficos se $G'_1$ e $G'_2$ são isomórficos. Informalmente: em $G'_1$ e $G'_2$ os nós adicionados não podem "interferir" no isomorfismo original porque seu grau é superior a $\max(\text{deg}(u_i))$

Vor
fonte