Выборка идеального совпадения в случайном порядке

Предположим , у меня есть граф с на (неизвестно) набор совершенных паросочетаний . Предположим, что это множество не пустое, тогда как трудно выбрать равномерно случайную выборку из ? Что если я в порядке с распределением, близким к равномерному, но не совсем равномерным, то существует ли эффективный алгоритм? $G$ $M(G)$ $G$ $M(G)$

algorithms complexity-theory matching sampling Артем Казнатчеев
источник

Вы знаете что-нибудь еще о

? Или, другими словами, вас могут заинтересовать какие-либо классы ограниченных графов?

G

$G$

Юхо

@Juho Я предпочитаю результаты для общих графов, в частности для плотных графов (поэтому то, что Ювал упоминает в своем ответе, кажется многообещающим). Я думаю, что раньше я видел некоторые результаты для плоских графиков. Однако, поскольку это общий вопрос, если у вас есть ответ на некоторые интересные семейства графиков, то, вероятно, все же стоит ответить на него, поскольку другие, которые ищут этот вопрос, возможно, захотят узнать.

Артем Казнатчеев

Просто чтобы прояснить, я предполагаю, что у вас нет

под рукой?

M (G)

$M(G)$

Рафаэль

@ Рафаэль, я думаю, вопрос был бы тривиальным, если бы ты это сделал. На самом деле, я думаю, что вопрос был бы относительно простым, если бы вы только что

, поскольку обычно существует соответствие между подсчетом и отбором проб. Или вы имели в виду «под рукой» каким-то другим способом?

| M (G) |

$|M(G)|$

Артем Казнатчеев

Понимаю. Я нашел вашу фразу двусмысленной, которую я пытался исправить. Я правильно понял?

Рафаэль

Ответы:

Существует классическая статья Джеррума и Синклера (1989) о выборке идеальных совпадений из плотных графиков. В другой классической работе Джеррума, Синклера и Вигоды (2004; pdf) обсуждается выборка идеальных совпадений из двудольных графов.

В обеих этих работах используются быстро перемешивающиеся цепи Маркова, и поэтому образцы являются практически почти однородными. Я предполагаю, что равномерная выборка затруднена.

Юваль Фильмус
источник

Если вы предполагаете, что ваш график плоский, то для этой задачи выборки существует процедура за полиномиальное время.

Во-первых, проблема подсчета числа совершенных совпадений в P для плоских графов. ( https://en.wikipedia.org/wiki/FKT_algorithm ) (Хорошее изложение этого факта можно найти в первой главе книги Джеррума «Подсчет, выборка и интеграция».)

$e$ $G$ $G \setminus e$ $e$ $G$ . Выберите границу в соответствии с этой вероятностью и продолжайте индуктивно.

(При этом используется тот факт, что сопоставления являются «самовосстанавливаемой» структурой, поэтому проблемы подсчета и проблемы равномерной выборки по сути одинаковы. Вы можете увидеть в JVV «Случайная генерация комбинаторных структур из равномерного распределения», чтобы узнать больше об этом точка зрения.)

Простое доказательство того, что это дает правильное распределение:

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

Лоренцо Найт
источник