Contando o número de ciclos hamiltonianos em gráficos cúbicos hamiltonianos?

15

É difícil encontrar uma aproximação constante do fator do ciclo mais longo em gráficos hamiltonianos cúbicos. Os gráficos hamiltonianos cúbicos possuem pelo menos dois ciclos hamiltonianos. $NP$

Quais são os limites superior e inferior mais conhecidos no número de ciclos hamiltonianos nos gráficos cúbicos hamiltonianos? Dado um gráfico hamiltoniano cúbico, qual é a complexidade de encontrar o número de ciclos hamiltonianos? É # -hard? $P$

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

20

A contagem de circuitos Hamiltonianos em um gráfico Hamiltoniano 3-regular é # P-completa, como segue.

Esboço de prova . A participação no #P é trivial, portanto, mostraremos apenas a dureza # P.

A Seção 3 de Liśkiewicz, Ogihara e Toda [LOT03] mostra que a contagem de circuitos hamiltonianos em um gráfico 3-regular (e de fato planar ao mesmo tempo) é # P-completa. Além disso, sua redução de # 3SAT mapeia a fórmula 3CNF satisfatória para gráficos hamiltonianos. Portanto, você pode reduzir o # 3SAT à contagem de circuitos hamiltonianos em um gráfico hamiltoniano 3-regular, primeiro adicionando uma solução trivial a uma dada fórmula 3CNF e depois reduzindo-a a contagem de circuitos hamiltonianos usando a redução em [LOT03]. QED .

[LOT03] Maciej Liśkiewicz, Mitsunori Ogihara e Seinosuke Toda. A complexidade da contagem de autoavaliações caminha em subgráficos de grades bidimensionais e hipercubos. Teoria da Computação , 304 (1–3): 129–156, julho de 2003. http://dx.doi.org/10.1016/S0304-3975(03)00080-X

Tsuyoshi Ito
fonte

Boa resposta. Você conhece algum limite superior ou limite inferior do número de ciclos hamiltonianos nos gráficos cúbicos hamiltonianos?

Mohammad Al-Turkistany

11

@turkistany: Você pode gerar um gráfico tridimensional com muitos circuitos hamiltonianos exponencialmente aplicando a redução acima a uma fórmula 3CNF com muitas tarefas satisfatórias exponencialmente (consulte o Corolário 6 de [LOT03] e a definição de “

reductions 2.2), embora eu suspeite que exista uma prova direta mais simples. Não conheço nenhum limite inferior, exceto 2 (que você já mencionou na pergunta) ou qualquer prova de que 2 seja o ideal.

\leq_{r-shift}^{p}

$\le^p_{\text{r-shift}}$

Tsuyoshi Ito

23

No meu artigo "O problema do vendedor ambulante para gráficos cúbicos" ( J. Graph Algorithms and Applications 11 (1): 61-81, 2007 ) provei um limite superior de ao número de ciclos hamiltonianos, conjecturou que o limite poderia ser melhorado para e encontrou uma família de gráficos que possuem exatamente mostrando que, se verdadeiro, o limite conjecturado seria apertado. Heidi Gebauer ("Sobre o número de ciclos de Hamilton em gráficos de graus delimitados", ANALCO 2008 ) melhorou o limite superior para . $2^{3n/8}$ $2^{n/3}$ $2^{n/3}$ $1.276^n$

Se alguém permite multigráficos, um ciclo que alterna entre ligações simples e duplas possui ciclos hamiltonianos, e isso é apertado. $2^{n/2}$

David Eppstein
fonte

Obrigado David pela boa resposta, gostaria de poder aceitar mais de uma resposta.

Mohammad Al-Turkistany

8

Alguns gráficos têm exatamente três circuitos hamiltonianos:

http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190060218/abstract

Se alguém começa com o gráfico plano do tetraedro, que contém exatamente três circuitos hamiltonianos, e cria um novo gráfico planar conectado em 3, truncando um único vértice, obtém um novo gráfico que possui exatamente três circuitos hamiltonianos. Se alguém continua a truncar um vértice de cada vez, obtém uma família de gráficos com exatamente três circuitos hamiltonianos.

Comentário adicional:

Também tem havido algum trabalho sobre a questão de quais gráficos, além de ciclos, possuem exatamente um circuito hamiltonion:

http://www3.interscience.wiley.com/journal/113386600/abstract

Um artigo de pesquisa muito bom sobre circuitos hationionais em tipos especiais de gráficos que possui uma seção que trata de números de circuitos hamiltonianos e corrige alguns problemas com o artigo acima:

http://ajc.maths.uq.edu.au/pdf/20/ajc-v20-p111.pdf

Joseph Malkevitch
fonte

Contando o número de ciclos hamiltonianos em gráficos cúbicos hamiltonianos?

Respostas: