Próbkowanie idealne dopasowanie równomiernie losowo

Załóżmy, że ma wykres o M ( G ) do (brak danych) zestawu doskonałych skojarzeń z G . Załóżmy, że ten zestaw nie jest pusty, to jak trudne jest jednorodne losowe pobieranie próbek z M ( G ) ? Co się stanie, jeśli nie mam nic przeciwko rozkładowi zbliżonemu do jednorodnego, ale niezupełnie jednorodnemu, to czy istnieje skuteczny algorytm?$G$$M(G)$$G$$M(G)$

Istnieje klasyczny artykuł Jerruma i Sinclaira (1989) na temat pobierania idealnych dopasowań z gęstych wykresów. Kolejna klasyczna praca Jerruma, Sinclaira i Vigody (2004; pdf) omawia próbkowanie idealnych dopasowań z dwustronnych grafów.

Oba te papiery używają szybkiego mieszania łańcuchów Markowa, więc próbki są prawie jednolite. Wyobrażam sobie, że jednolite pobieranie próbek jest trudne.

Jeśli założysz, że twój wykres jest płaski, istnieje procedura wielomianowa dla tego problemu z próbkowaniem.

Po pierwsze, problem zliczania liczby idealnych dopasowań leży w P dla grafów płaskich. ( https://en.wikipedia.org/wiki/FKT_alameterm ) (Dobra prezentacja tego faktu znajduje się w pierwszym rozdziale książki Jerrum o liczeniu, próbkowaniu i integracji).

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

(Wykorzystuje to fakt, że dopasowania są strukturą „samoregenerowalną”, więc problemy z liczeniem i problemy z jednolitym próbkowaniem są zasadniczo takie same. Możesz zobaczyć JVV „Losowe generowanie struktur kombinatorycznych z jednolitego rozkładu”, aby uzyskać więcej informacji na ten temat punkt widzenia.)

Prosty dowód, że daje to prawidłową dystrybucję:

$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)$