Classes de gráfico em que os problemas do Ciclo Hamiltoniano e do Caminho Hamiltoniano têm complexidade diferente

Ao pesquisar o Sistema de informações sobre classes de gráfico e suas inclusões , encontrei várias classes de gráfico para as quais o problema do ciclo hamiltoniano é NP-completo, enquanto a complexidade dos problemas do caminho hamiltoniano NÃO é conhecida. Algumas dessas classes são gráficos bipartidos de grau máximo 3, gráficos de grade grau máximo 3 e gráficos planares cúbicos com 2 conexões. Este fenômeno também se aplica a gráficos circulares e gráficos de grade triangular.

Existe uma atualização para a complexidade do problema do caminho hamiltoniano nessas classes? Existe uma explicação para esse fenômeno?

EDIT : Encontrei no banco de dados de classes de gráficos um caso estranho de gráficos de grade sólida, onde o problema do ciclo hamiltoniano está em enquanto o problema do caminho hamiltoniano é de complexidade desconhecida . $P$

cc.complexity-theory graph-theory Mohammad Al-Turkistany
fonte

Gostaria de saber se existe uma classe gráfica interessante para a qual a HP está em mas HC é completo.

P

$P$

N P

$NP$

Mohammad Al-Turkistany

Em geral, existe alguma classe de gráfico para a qual um dos problemas (HC e HP) é completo e o outro está em ou em ? Estou procurando resultados publicados para problemas de HC e HP.

N P

$NP$

P

$P$

N P I

$NPI$

Mohammad Al-Turkistany

Pelo que vale a pena (não muito), o Caminho Hamiltoniano e o Ciclo Hamiltoniano têm complexidade diferente nas árvores: o ciclo é trivial, mas o caminho requer uma varredura linear para verificar se existe um vértice de grau superior a dois.

David Richerby

É improvável que a HP esteja em e HC seja completo para qualquer classe de gráfico, pois há uma redução de Cook de HC para HP que faz no máximo chamadas para o oráculo da HP. A verdadeira questão é se existe uma redução de Karp ( ).

P

$P$

N P

$NP$

O (| E |)

$O(|E|)$

H C <_{P}^{m} H P

$HC<_P^m HP$

Mohammad Al-Turkistany

Respostas:

O problema do caminho hamiltoniano em gráficos de grade com grau máximo 3 é NP-completo. A prova está em CH Papadimitriou e UV Vazirani, Sobre dois problemas geométricos relacionados ao problema do vendedor ambulante, Journal of Algorithms, Volume 5, Volume 5, Edição 2, Junho de 1984, Páginas 231–246 (Teorema 2)

Marzio De Biasi
fonte

Obrigado Marzio, eles estão usando a mesma definição usada no banco de dados para gráficos de grade? (uma vez que são diferentes definições na literatura)

Mohammad Al-Turkistany

Um gráfico de grade é uma finito, subgráfico induzida pelo nó de

, o gráfico infinito cujo conjunto vértice consiste em todos os pontos do plano de coordenadas de número inteiro e em que dois vértices estão ligados, se e somente se a distância euclidiana entre eles é um; assim um gráfico grade pode ter "buracos" e o teorema é provado por (restritas a) gráficos de grelha na qual os vértices tenham o máximo de grau 3.

G^{\infty}

$G^\infty$

Marzio de Biasi

Obrigado Marzio, então, para esta classe, HC e HP têm a mesma complexidade.

Mohammad Al-Turkistany

@ MohammadAl-Turkistany: outra observação: os gráficos de grade (e gráficos com grau máximo 3) também são bipartidos; portanto, a HP deve estar completa com NP para gráficos bipartidos com grau máximo 3 também.

Marzio De Biasi

Houve uma atualização no sistema de informações sobre classes de gráfico e suas inclusões. Agora, o problema do ciclo hamiltoniano e do caminho hamiltoniano são declarados NP-completos em gráficos planares cúbicos de 2 conexões.

No entanto, as complexidades computacionais dos problemas de HC e HP são listadas desconhecidas para um problema e NP-completas para o outro em gráficos circulares , gráficos de grade triangular e gráficos de grade sólidos .

Mohammad Al-Turkistany
fonte

Você diz "... as complexidades dos problemas de HC e HP ainda são diferentes ..."; talvez seja melhor dizer que "para essas classes de gráficos HC é NPC, mas a HP ainda tem complexidade desconhecida"

Marzio De Biasi /

@MarzioDeBiasi Obrigado pelo seu valioso comentário. Eu editei para refletir sua sugestão.

Mohammad Al-Turkistany

Perco alguma coisa? HC é tempo polinomial solucionável em gráficos de grade sólida. ieeexplore.ieee.org/document/646138

Saeed