Hamiltonicidade de gráficos k-regulares

24

Sabe-se que é NP-completo testar se existe um ciclo hamiltoniano em um gráfico tridimensional, mesmo que seja plano (Garey, Johnson e Tarjan, SIAM J. Comput. 1976) ou bipartido (Akiyama, Nishizeki, e Saito, J. Inform. Proc. 1980) ou para testar se existe um ciclo hamiltoniano em um gráfico de 4 regulares, mesmo quando é o gráfico formado por um arranjo de curvas de Jordan (Iwamoto e Toussaint, IPL 1994).

Para qual outro k é conhecido como NP-completo para testar a Hamiltonicidade de gráficos k-regulares?

O caso particular em que estou interessado é em gráficos regulares de 6, com a condição adicional de que o gráfico tenha um número ímpar de vértices. Se esse caso puder ser mostrado como NP-completo (ou polinomial), isso terá impacto em um problema de desenho de gráfico descrito em http://arxiv.org/abs/1009.0579 . A condição "número ímpar de vértices" é porque o que eu realmente quero saber é, para gráficos regulares, se o gráfico contém um ciclo hamiltoniano ou um fator bipartido de 2 fatores; mas ter um número ímpar de vértices elimina a possibilidade de um fator bipartido de 2 fatores, deixando apenas a possibilidade de um ciclo hamiltoniano.

David Eppstein
fonte

Respostas:

15

O primeiro passo é assumir que o gráfico tenha um número par de vértices. No segundo estágio, estenderemos a construção, de modo que se k for par, mostraremos como transformar o gráfico em ter um número ímpar de vértices.

A solução é um refinamento da idéia sugerida na outra resposta.

Primeira parte

Reivindicação: Dado umk gráfico regular com número par de vértices, pode-se calcular um gráfico H que é ( k + 1 ) -regular, e H é Hamiltoniano se G é Hamiltoniano.GH(k+1)HG

kGG1G2vV(G)v1v2k+2vvvv1vv2v. Deixe denotar esse componente para .C(v)v

Repita isso para todos os vértices de e deixe denotar o gráfico resultante.GH

Claramente, o gráfico é regular. Afirmamos que é Hamiltoniano se e somente se é Hamiltoniano.Hk+1HG

Uma direção é clara. Dado um ciclo Hambiltonian em , que podem traduzir-lo em um ciclo em . De fato, sempre que o ciclo visita um vértice , nós o interpretamos como passando de para (ou vice-versa) enquanto visitamos todos os vértices em . Como tal, isto resulta num ciclo hamiltoniano em . (Observe que é aqui que estamos usando o fato de que o número original de vértices é par - se o ciclo for ímpar, isso será interrompido.)GHvv1v2C(v)H

Como para a outra direcção, considere um ciclo hamiltoniano em . Deve ser que seja visitado por uma parte do ciclo que começa em , visite todos os vértices de e saia de (ou a opção simétrica). De fato, o ciclo hamiltoniano não pode entrar e sair do mesmo . Como tal, um ciclo hamiltoniano em como uma interpretação natural como um ciclo hamiltoniano em . QED.HC(v)v1C(v)v2viHG

Segunda parte

Como observado abaixo por Tsuyoshi, qualquer gráfico regular com número par de vértices. Como tal, o problema é difícil para um gráfico de regiões com número par de vértices. Nomeadamente, a redução acima mostra que o problema é difícil para qualquer gráfico em , embora o gráfico resultante tenha um número par de vértices.3k

Observamos que isso implica que o seguinte problema é NP-difícil.

Problema A: Decidindo se um gráfico k-regular com número par de vértices tem um ciclo hamiltoniano passando por uma aresta específica .Ge

No entanto, se receber uma instância , podemos reduzi-la ao problema desejado. De fato, substituímos a aresta por uma clique de vértices, como antes de excluir uma aresta na clique e conectar seus dois pontos finais aos pontos finais de , removendo do gráfico. Claramente, para o novo gráfico :k(G,e)ek+1eeH

  • H é regular.k
  • H é hamiltoniano se for hamiltoniano com um ciclo usando .Ge
  • H tem vértices => possui um número ímpar de vértices.|V(G)|+k+1H

Observe que um gráfico regular, para ímpar, deve ter um número par de vértices (apenas conte as arestas). Assim, não há gráficos regulares com número ímpar de vértices, com sendo ímpar.kkkk


Resultado

É NP-Difícil decidir se um gráfico regular possui um ciclo hamiltoniano para . O problema permanece NP-Hard, mesmo se o gráfico tiver um número ímpar de vértices.kk3


Claro, é sempre possível que cometi algum erro estúpido ...


Exercício

Se queremos passar de um gráfico que é regular para um gráfico que é (digamos) regular, o gráfico resultante da aplicação da redução acima resulta repetidamente em um gráfico com um tamanho que depende exponencialmente de . Mostra, que um dado -Regular gráfico , e , pode-se construir um gráfico de que é -Regular e o seu tamanho é polinomial em e , em que é o número de vértices de . Além disso, é hamiltoniano se e somente se for hamiltoniano.k2kkkGi>2H(k+i)k,innGGH

(Estou publicando isso como um exercício, não uma pergunta, pois sei como resolver isso.)

Sariel Har-Peled
fonte
1
Ótimo! Eu acho que essa resposta de fato resolve a primeira pergunta “Para qual outro k é conhecido como NP-completo para testar a Hamiltonicidade dos gráficos k-regulares?” Porque os gráficos tridimensionais têm um número par de vértices, e o gráfico H feito por essa transformação também possui um número par de vértices se G tiver um número par de vértices.
Tsuyoshi Ito
Mas, a menos que eu esteja enganado, o mesmo contra-exemplo à prova de Robin é um contra-exemplo a essa prova. Seja G o caminho em 2 vértices. Então, o procedimento aqui cria H, que é um ciclo 9, que é hamiltoniano.
Emil
Como eu disse em relação à resposta de Robin, o problema é que, quando você tenta "projetar" o ciclo de Hamilton de H para G, o ciclo pode acabar não sendo um ciclo, porque remonta a onde esteve.
Emil
@Emil: Eu acho que o caminho em 2 vértices é realmente um caso especial, porque ele tem um circuito hamiltoniano se pudermos usar a mesma borda mais de uma vez.
Tsuyoshi Ito
1
@Sariel Har-Peled: Em todo gráfico, o número de vértices ímpares (ou seja, vértices de grau ímpar) é par. Portanto, todos os gráficos tridimensionais têm um número par de vértices. Eu escrevi um argumento desnecessariamente complicado sem perceber isso na primeira versão do comentário (que modifiquei em menos de 5 minutos); então, desculpe-me se você ler meu comentário antigo e ficou confuso com ele.
Tsuyoshi Ito
1

EDIT: Esta prova está errada, como apontado nos comentários. (Devo excluir a postagem?)

Parece intuitivamente que se a Hamiltonicidade é NP-difícil para gráficos k-regulares, também deve ser NP-difícil para gráficos regulares (k + 1). Aqui está uma redução do envelope, o que parece bom para mim, mas é claro que pode haver um erro.

Seja G um gráfico k-regular. Seja G 'um produto cartesiano gráfico de G e uma aresta. Em outras palavras, G 'é o gráfico que possui duas cópias de G e todos os vértices estão conectados à sua cópia. G 'é agora (k + 1) regular, já que cada vértice tem 1 aresta extra.

Reivindicação: G tem um ciclo hamiltoniano se e somente se G 'tiver um ciclo hamiltoniano.

Prova: se G tem um ciclo hamiltoniano, é fácil ver que G 'também tem um. Diga (u, v) é uma vantagem no ciclo hamiltoniano. Atravesse o ciclo de u até v sem usar essa aresta e agora, em vez de usar a aresta, vá para v 'de v, em que v' é o vértice correspondente a v na cópia de G. Agora, atravesse o ciclo na ordem inversa neste gráfico, que nos trará de volta a você '. Agora vá de u 'para u, o que completa o ciclo.

Se G 'tem um ciclo hamiltoniano começando no vértice u, considere a mesma sequência de travessias em G. Toda vez que uma movimentação é feita para um vértice adjacente no mesmo gráfico, fazemos a mesma jogada em G. Toda vez que uma movimentação é feita para o vértice correspondente no outro gráfico, não fazemos nada. Como todo movimento é válido no gráfico G e o ciclo termina no vértice u, esse é um ciclo hamiltoniano.

Robin Kothari
fonte
1
Não vejo como funciona o segundo parágrafo da prova. Se abandonarmos a condição de que G é k-regular, deixar G ser um caminho dá um contra-exemplo a uma alegação de que se G 'é hamiltoniano, G também é hamiltoniano.
Tsuyoshi Ito
1
Estou um pouco preocupado com o último parágrafo aqui. Quando o ciclo de Hamilton para G 'é "projetado" (se essa é a palavra certa!) Para G, podemos ter uma situação em que o ciclo refaz seus passos.
Emil
@ Tsuyoshi: você tem um contra-exemplo: basta seguir um caminho regular - o caminho com dois vértices.
Emil
@ Tsuyoshi: Você está certo. A prova está errada. Devo excluir a resposta? Temos uma política sobre isso?
Robin Kothari
@ Robin, acho que seu post deve ser deixado agora que gerou alguma discussão. Certamente ilustra que esse é um problema incômodo.
Emil