¿Cómo producir un gráfico aleatorio que no tenga un ciclo hamiltoniano?

Deje que la clase A denote todas las gráficas de tamaño que tienen un ciclo hamiltoniano. Es fácil producir un gráfico aleatorio a partir de esta clase: tome nodos aislados, agregue un ciclo hamiltoniano aleatorio y luego agregue bordes aleatoriamente. $n$ $n$

Supongamos que la clase B denota todas las gráficas de tamaño que no tienen un ciclo hamiltoniano. ¿Cómo podemos elegir un gráfico aleatorio de esta clase? (o hacer algo parecido a eso) $n$

ds.algorithms graph-theory Jagadish
fuente

¿Cómo está claro que el primer procedimiento produce gráficas uniformemente al azar? Está claro que siempre produce gráficos hamiltonianos, pero dado que agrega bordes al azar más adelante, puede introducir más ciclos hamiltonianos, haciendo que algunos gráficos aparezcan con más frecuencia que otros.

Robin Kothari

Esto es correcto, pero no se solicitó una distribución uniforme (si está implícita).

Raphael

Sí, no me importa la uniformidad. Me gustaría dar a cada gráfico de la familia de gráficos no hamiltonianos alguna posibilidad de ser elegido. El problema con el muestreo uniforme es bastante básico: AFAIK, no sabemos cómo muestrear uniformemente de una familia de gráficos de tamaño n, y mucho menos aquellos con ciclos hamiltonianos.

Jagadish

Respuestas:

Esto es imposible (a menos que NP = coNP) ya que, en particular, implica una función de tiempo múltiple cuyo rango son los gráficos no hamiltonianos (la función va de la cadena aleatoria al gráfico de salida), lo que a su vez implicará una prueba NP de no Hamiltonianicity (para demostrar que G no tiene un circuito hamiltoniano, muestre x que se le asigne).

Noam
fuente

Asume que dicha función está en la clase de gráficos no hamiltonianos. Este es solo el caso si queremos que la distribución sea uniforme. Vea también el comentario de Aaron a continuación: cstheory.stackexchange.com/questions/562/…

Ohad Kammar el

Esto no supone nada acerca de las probabilidades de elegir cada gráfico (como si fuera uniforme), solo que los gráficos que pueden generar los algoritmos son exactamente los no hamiltonianos (en). Si permite el error en cualquier lado, entonces de hecho esto puede ser posible.

Noam

Estoy de acuerdo, lo que importa no es la uniformidad de la distribución, sino el hecho de que todos los gráficos no hamiltonianos tienen una probabilidad distinta de cero. Si incluso uno de ellos tiene probabilidad cero, su prueba no se aplica (sin más conocimiento sobre el soporte de la distribución).

Ohad Kammar el

@Ohad: si se pierde uno de ellos, puede agregarlo a una tabla de búsqueda. Creo que los problemas solo comienzan si pierdes una fracción positiva de ellos, pero luego no estás muestreando de manera uniforme.

Emil

Si su algoritmo produce una distribución uniforme en los gráficos no hamiltonianos con probabilidad

y un gráfico hamiltoniano con probabilidad

, y

medida que el tamaño de entrada va a

, entonces creo que debería poder combinar este algoritmo con funciones hash aleatorias para encontrar una prueba interactiva de ronda constante de no Hamiltonicidad. Esto implicaría que la jerarquía polinómica se derrumba

1 - ϵ

$1-\epsilon$

ϵ

$\epsilon$

ϵ \to 0

$\epsilon \rightarrow 0$

\infty

$\infty$

Peter Shor

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

$n$

Aaron Roth
fuente

Esta es una buena idea, aunque podemos omitir todo el algoritmo probabilístico para encontrar el ciclo de Ham. La pregunta no pide que el procedimiento de muestreo se ejecute en el polytime esperado ni nada. Así que cree un gráfico aleatorio a partir de su distribución favorita, determine si es hamiltoniano con algún algoritmo exacto, y si es hamiltoniano, deséchelo y repita el proceso. Si la distribución utilizada fue la distribución uniforme sobre todos los gráficos etiquetados, esto realmente producirá todos los gráficos etiquetados no hamiltonianos con probabilidad uniforme.

JimN

La primera tarea es fácil porque los gráficos hamiltonianos son fáciles de verificar. Sin embargo, no se conocen pruebas cortas que puedan verificarse eficientemente para presenciar que un gráfico dado no sea hamiltoniano.

Mohammad Al-Turkistany
fuente

Creo que la respuesta de Turquía plantea una pregunta interesante. En general, ¿es posible muestrear uniformemente de un lenguaje que es co-NP-completo?

Suresh Venkat

.... y Noam responde que en negativo.

Suresh Venkat