Comment produire un graphe aléatoire qui n'a pas de cycle hamiltonien?

Soit la classe A tous les graphes de taille qui ont un cycle hamiltonien. Il est facile de produire un graphe aléatoire à partir de cette classe - prenez nœuds isolés, ajoutez un cycle hamiltonien aléatoire, puis ajoutez des bords au hasard. $n$ $n$

Soit la classe B tous les graphes de taille qui n'ont pas de cycle hamiltonien. Comment pouvons-nous choisir un graphique aléatoire dans cette classe? (ou faites quelque chose de proche) $n$

ds.algorithms graph-theory Jagadish
la source

Comment est-il clair que la première procédure produit des graphiques uniformément au hasard? Il est clair qu'il produit toujours des graphes hamiltoniens, mais comme vous ajoutez des arêtes au hasard plus tard, vous pouvez introduire plus de cycles hamiltoniens, faisant apparaître certains graphes plus fréquemment que d'autres.

Robin Kothari

C'est vrai, mais une distribution uniforme n'a pas été demandée (si cela est peut-être implicite).

Raphael

Oui, je me fiche de l'uniformité. Je voudrais donner à chaque graphique de la famille des graphiques non hamiltoniens une chance d'être sélectionné. Le problème de l'échantillonnage uniforme est assez basique: AFAIK, nous ne savons pas comment échantillonner uniformément à partir d'une famille de graphiques de taille n, sans parler de ceux avec des cycles hamiltoniens.

Jagadish

Réponses:

C'est impossible (sauf NP = coNP) car cela implique notamment une fonction poly-temps dont la plage est les graphes non hamiltoniens (la fonction va de la chaîne aléatoire au graphe de sortie), ce qui à son tour impliquera une NP-proof de non-hamiltonianicité (pour prouver que G n'a pas de circuit hamiltonien, montrez x qui lui correspond.)

Noam
la source

Vous supposez qu'une telle fonction appartient à la classe des graphes non hamiltoniens. Ce n'est le cas que si nous voulons que la distribution soit uniforme. Voir aussi le commentaire d'Aaron ci-dessous: cstheory.stackexchange.com/questions/562/…

Ohad Kammar

Cela ne suppose rien sur les probabilités de choisir chaque graphique (comme s'il était uniforme), mais seulement que les graphiques qui peuvent être sortis par les algorithmes sont exactement ceux non hamiltoniens (sur). Si vous autorisez une erreur de chaque côté, cela peut en effet être possible.

Noam

Je suis d'accord, ce n'est pas l'uniformité de la distribution qui importe, mais plutôt le fait que tous les graphiques non hamiltoniens ont une probabilité non nulle. Si même l'un d'entre eux a une probabilité nulle, votre preuve ne s'applique pas (sans plus de connaissances sur le support de la distribution).

Ohad Kammar

@Ohad: si l'un d'eux est oublié, vous pouvez simplement l'ajouter à une table de recherche. Je pense que les problèmes ne commencent que si vous en manquez une fraction positive, mais vous n'échantillonnez pas uniformément.

Emil

1 - ϵ

$1-\epsilon$

ϵ

$\epsilon$

ϵ \to 0

$\epsilon \rightarrow 0$

\infty

$\infty$

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

$n$

Aaron Roth
la source

C'est une bonne idée, bien que nous puissions ignorer tout l'algorithme probabiliste pour trouver le cycle de Ham. La question ne demande pas que la procédure d'échantillonnage s'exécute dans le polytime attendu ou quoi que ce soit. Créez donc un graphique aléatoire à partir de votre distribution préférée, déterminez s'il s'agit d'un hamiltonien avec un algorithme exact, et s'il est hamiltonien, jetez-le et répétez le processus. Si la distribution utilisée était la distribution uniforme sur tous les graphiques étiquetés, cela produira en fait chaque graphique étiqueté non hamiltonien avec une probabilité uniforme.

JimN

La première tâche est facile car les graphiques hamiltoniens sont faciles à vérifier. Cependant, il n'existe aucune preuve courte connue qui puisse être efficacement vérifiée pour constater que le graphe donné n'est pas hamiltonien.

Mohammad Al-Turkistany
la source

Je pense que la réponse de la Turquie soulève une question intéressante. En général, est-il possible d'échantillonner uniformément à partir d'une langue co-NP-complete?

Suresh Venkat

.... et Noam répond à cela par la négative.

Suresh Venkat