Como produzir um gráfico aleatório que não possui um ciclo hamiltoniano?

Deixe a classe A denotar todos os gráficos de tamanho que possuem um ciclo hamiltoniano. É fácil produzir um gráfico aleatório dessa classe - pegue nós isolados, adicione um ciclo hamiltoniano aleatório e adicione arestas aleatoriamente. $n$ $n$

Deixe a classe B denotar todos os gráficos de tamanho que não possuem um ciclo hamiltoniano. Como podemos escolher um gráfico aleatório dessa classe? (ou faça algo parecido com isso) $n$

ds.algorithms graph-theory Jagadish
fonte

Como está claro que o primeiro procedimento produz gráficos uniformemente ao acaso? É claro que ele sempre produz gráficos hamiltonianos, mas, como você adiciona arestas aleatoriamente mais tarde, pode introduzir mais ciclos hamiltonianos, fazendo alguns gráficos aparecerem com mais frequência do que outros.

Robin Kothari

Isso está certo, mas uma distribuição uniforme não foi solicitada (se talvez implícita).

Raphael

Sim, eu não ligo para a uniformidade. Eu gostaria de dar a todos os gráficos da família de gráficos não Hamiltonianos alguma chance de serem escolhidos. O problema com a amostragem uniforme é bastante básico: AFAIK, não sabemos como amostrar uniformemente a partir de uma família de gráficos de tamanho n, e muito menos daqueles com ciclos hamiltonianos.

Jagadish

Respostas:

Isso é impossível (a menos que NP = coNP), pois, em particular, isso implica uma função de politempo cujo intervalo são os gráficos não Hamiltonianos (a função vai da sequência aleatória para o gráfico de saída), o que, por sua vez, implica uma prova de NP de não-Hamiltonianicidade (para provar que G não tem um circuito Hamiltoniano, mostre x que mapeia para ele).

Noam
fonte

Você assume que essa função está ligada à classe de gráficos não Hamiltonianos. Este é apenas o caso se queremos que a distribuição seja uniforme. Veja também o comentário de Aaron abaixo: cstheory.stackexchange.com/questions/562/…

Ohad Kammar

Isso não pressupõe nada sobre as probabilidades de escolher cada gráfico (como é uniforme), apenas que os gráficos que podem ser gerados pelos algoritmos são exatamente os não Hamiltonianos (em). Se você permitir erros de ambos os lados, isso poderá ser possível.

Noam

Concordo que não é a uniformidade da distribuição que importa, mas o fato de que todos os gráficos não Hamiltonianos têm probabilidade diferente de zero. Se mesmo um deles tiver probabilidade zero, sua prova não se aplica (sem mais conhecimentos sobre o suporte da distribuição).

Ohad Kammar

@ Had: se um deles estiver faltando, você poderá adicionar isso a uma tabela de consulta. Eu acho que os problemas só começam se você perder uma fração positiva deles, mas então você não está amostrando uniformemente.

Emil

Se o seu algoritmo produz uma distribuição uniforme nos gráficos não hamiltonianos com probabilidade

e um gráfico hamiltoniano com probabilidade

, e

quando o tamanho da entrada for

, acho que você deve poder combinar esse algoritmo com funções de hash aleatório para encontrar uma prova interativa de não-Hamiltonicidade, redonda e constante. Isso implicaria que a hierarquia polinomial entra em colapso

1 - ϵ

$1-\epsilon$

ϵ

$\epsilon$

ϵ \to 0

$\epsilon \rightarrow 0$

\infty

$\infty$

Peter Shor

$G_{n,m}$ $m$ $n$

$n$

Aaron Roth
fonte

Essa é uma boa idéia, embora possamos pular todo o algoritmo probabilístico para encontrar o ciclo de Ham. A pergunta não pede que o procedimento de amostragem seja executado no polytime esperado ou algo assim. Portanto, crie um gráfico aleatório a partir de sua distribuição favorita, determine se é hamiltoniano com algum algoritmo exato e, se for hamiltoniano, descarte-o e repita o processo. Se a distribuição usada foi a distribuição uniforme em todos os gráficos rotulados, isso realmente produzirá todos os grafos não Hamiltonianos com probabilidade uniforme.

JimN 29/11

A primeira tarefa é fácil porque os gráficos hamiltonianos são fáceis de verificar. No entanto, não há prova curta conhecida que possa ser eficientemente verificada para testemunhar que o gráfico fornecido não é hamiltoniano.

Mohammad Al-Turkistany
fonte

Eu acho que a resposta do Turquistão traz uma pergunta interessante. Em geral, é possível amostrar uniformemente a partir de um idioma que seja co-NP-completo?

Suresh Venkat

.... e Noam responde que no negativo.

Suresh Venkat