Échantillonnage de la correspondance parfaite uniformément au hasard

Supposons que j'ai un graphe avec le (inconnu) ensemble de couplages parfaits de . Supposons que cet ensemble ne soit pas vide, alors à quel point est-il difficile d'échantillonner uniformément au hasard à partir de ? Et si je suis d'accord avec une distribution proche de l'uniforme, mais pas tout à fait uniforme, existe-t-il un algorithme efficace? $G$ $M(G)$ $G$ $M(G)$

algorithms complexity-theory matching sampling Artem Kaznatcheev
la source

Savez-vous quelque chose de plus sur

? Ou en d'autres termes, seriez-vous même intéressé par des classes de graphes restreintes?

G

$G$

Juho

@Juho Je préfère les résultats pour les graphiques généraux, en particulier pour les graphiques denses (donc ce que Yuval mentionne dans sa réponse semble prometteur). J'ai déjà vu des résultats pour des graphes planaires, je pense. Cependant, comme il s'agit d'une question générale, si vous avez une réponse pour certaines familles de graphiques intéressantes, cela vaut probablement la peine de répondre, car d'autres qui recherchent cette question aimeraient peut-être le savoir.

Artem Kaznatcheev

Juste pour être clair, je suppose que vous n'avez pas

à portée de main?

M (G)

$M(G)$

Raphael

@Raphael Je pense que la question serait triviale si vous le faisiez. En fait, je pense que la question serait relativement simple si vous veniez d'avoir

, car il existe généralement une correspondance entre le comptage et l'échantillonnage. Ou vouliez-vous dire "à portée de main" d'une autre manière?

| M (G) |

$|M(G)|$

Artem Kaznatcheev

Je vois. J'ai trouvé votre formulation ambiguë, que j'ai essayé de corriger. Ai-je bien compris?

Raphael

Réponses:

Il existe un article classique de Jerrum et Sinclair (1989) sur l'échantillonnage des correspondances parfaites à partir de graphiques denses. Un autre article classique de Jerrum, Sinclair et Vigoda (2004; pdf) traite de l'échantillonnage des correspondances parfaites à partir de graphiques bipartites.

Ces deux papiers utilisent des chaînes de Markov à mélange rapide, et les échantillons ne sont donc que presque uniformes. J'imagine qu'un échantillonnage uniforme est difficile.

Yuval Filmus
la source

Si vous supposez que votre graphique est planaire, il existe une procédure temporelle polynomiale pour ce problème d'échantillonnage.

Tout d'abord, le problème du comptage du nombre de correspondances parfaites est dans P pour les graphes planaires. ( https://en.wikipedia.org/wiki/FKT_algorithm ) (Une bonne exposition de ce fait peut être trouvée dans le premier chapitre du livre de Jerrum sur le comptage, l'échantillonnage et l'intégration.)

$e$ $G$ $G \setminus e$ $e$ $G$

(Cela profite du fait que les appariements sont une structure "auto-réductible", donc les problèmes de comptage et les problèmes d'échantillonnage uniforme sont essentiellement les mêmes. Vous pouvez voir JVV "Génération aléatoire de structures combinatoires à partir d'une distribution uniforme" pour plus d'informations à ce sujet. point de vue.)

Une simple preuve que cela donne la bonne distribution:

$c(H)$ $H$ $n!$ $n = H/2$

$e_1, \ldots, e_n$

$\frac{ c(G \setminus e_1)}{c(G)} \frac{ c(G \setminus \{e_1, e_2\} )}{c(G \setminus e_1)} \ldots \frac{ c(G \setminus \{e_1, \ldots, e_{n-1} \}) }{c(G \setminus \{ e_1, \ldots, e_{n-2} \} )}$

$c(G \setminus \{e_1, \ldots, e_{n-1} \}) = 1$ , since $G \setminus \{e_1, \ldots, e_{n-1} \}$ is just the edge $e_n$ . So this product telescopes and leaves $1 / c(G)$ .

Lorenzo Najt
la source