Amostragem perfeita de correspondência uniforme de forma aleatória

Suponha que eu tenho um gráfico com do (desconhecido) conjunto de matchings perfeitos de . Suponha que este conjunto não esteja vazio; então, como é difícil amostrar uniformemente aleatoriamente a partir de ? E se eu estiver bem com uma distribuição que seja quase uniforme, mas não muito uniforme, existe um algoritmo eficiente? $G$ $M(G)$ $G$ $M(G)$

algorithms complexity-theory matching sampling Artem Kaznatcheev
fonte

Você sabe mais alguma coisa sobre

? Ou, em outras palavras, você estaria interessado em alguma classe de gráfico restrita?

G

$G$

Juho

@ Juho Eu prefiro resultados para gráficos gerais, em especial para gráficos densos (então o que Yuval menciona em sua resposta parece promissor). Eu já vi alguns resultados para gráficos planares antes, eu acho. No entanto, como essa é uma pergunta geral, se você tiver uma resposta para algumas famílias interessantes de gráficos, provavelmente ainda vale a pena responder, pois outras pessoas que pesquisam essa pergunta podem querer saber.

Artem Kaznatcheev 25/03

Só para deixar claro, eu suponho que você não tem

na mão?

M (G)

$M(G)$

Raphael

@ Rafael Acho que a pergunta seria trivial se você fizesse. Na verdade, acho que a pergunta seria relativamente direta se você tivesse

, pois geralmente existe uma correspondência entre contagem e amostragem. Ou você quis dizer "na mão" de alguma outra maneira?

| M (G) |

$|M(G)|$

Artem Kaznatcheev 26/03

Entendo. Achei seu fraseado ambíguo, que tentei corrigir. Eu entendi direito?

Raphael

Respostas:

Existe um artigo clássico de Jerrum e Sinclair (1989) sobre amostragem de combinações perfeitas de gráficos densos. Outro artigo clássico de Jerrum, Sinclair e Vigoda (2004; pdf) discute a amostragem de combinações perfeitas de gráficos bipartidos.

Ambos os papéis usam cadeias Markov de mistura rápida e, portanto, as amostras são quase uniformes. Eu imagino que a amostragem uniforme seja difícil.

Yuval Filmus
fonte

Se você assumir que seu gráfico é plano, existe um procedimento de tempo polinomial para esse problema de amostragem.

Primeiro, o problema de contar o número de combinações perfeitas está em P para gráficos planares. ( https://en.wikipedia.org/wiki/FKT_algorithm ) (Uma boa exposição desse fato pode ser encontrada no primeiro capítulo do livro de Jerrum sobre Contagem, Amostragem e Integração.)

Em seguida, para cada aresta $e$ de $G$ , conte o número de combinações perfeitas de $G \setminus e$ . Isso pode ser transformado na probabilidade de uma correspondência perfeita uniforme contém $e$ - basta dividir pelo número de emparelhamentos perfeitos em $G$ . Faça uma amostra de uma aresta de acordo com essa probabilidade e continue indutivamente.

(Isso está tirando vantagem do fato de as correspondências serem uma estrutura "auto-redutível", portanto, problemas de contagem e problemas de amostragem uniforme são essencialmente os mesmos. Você pode ver JVV "Geração aleatória de estruturas combinatórias a partir de uma distribuição uniforme" para obter mais informações sobre isso. ponto de vista.)

Uma prova simples de que isso fornece a distribuição correta:

$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$ $G \setminus \{e_1, \ldots, e_{n-1} \}$ $e_n$ $1 / c(G)$

Lorenzo Najt
fonte