Die perfekte Übereinstimmung der Stichproben erfolgt nach dem Zufallsprinzip

Angenommen , ich habe einen Graphen mit der (unbekannt) Reihe von perfekt passenden . Angenommen, diese Menge ist nicht leer. Wie schwierig ist es dann, aus gleichmäßige Zufallsauswahl zu ? Was ist, wenn ich mit einer Verteilung einverstanden bin, die nahezu einheitlich, aber nicht ganz einheitlich ist? Gibt es dann einen effizienten Algorithmus? $G$ $M(G)$ $G$ $M(G)$

algorithms complexity-theory matching sampling Artem Kaznatcheev
quelle

Wissen Sie mehr über

? Oder mit anderen Worten, wären Sie überhaupt an eingeschränkten Grafikklassen interessiert?

G

$G$

Juho

@Juho Ich bevorzuge Ergebnisse für allgemeine Grafiken, insbesondere für dichte Grafiken (was Yuval in seiner Antwort erwähnt, scheint also vielversprechend zu sein). Ich denke, ich habe schon einige Ergebnisse für ebene Graphen gesehen. Da es sich jedoch um eine allgemeine Frage handelt und Sie eine Antwort auf einige interessante Familien von Diagrammen haben, lohnt es sich wahrscheinlich immer noch, Antworten zu geben, da andere, die nach dieser Frage suchen, dies möglicherweise wissen möchten.

Artem Kaznatcheev

Um es klar zu sagen, ich nehme an, Sie haben kein

zur Hand?

M (G)

$M(G)$

Raphael

@Raphael Ich denke, die Frage wäre trivial, wenn du es tust. Tatsächlich denke ich, dass die Frage relativ einfach wäre, wenn Sie es nur

, da in der Regel eine Entsprechung zwischen Zählen und Abtasten besteht. Oder meintest du "zur Hand" auf eine andere Weise?

| M (G) |

$|M(G)|$

Artem Kaznatcheev

Aha. Ich fand Ihre Formulierung nicht eindeutig, was ich zu korrigieren versuchte. Habe ich es richtig gesagt?

Raphael

Antworten:

Es gibt eine klassische Arbeit von Jerrum und Sinclair (1989) über die Auswahl perfekter Übereinstimmungen aus dichten Graphen. Ein weiteres klassisches Papier von Jerrum, Sinclair und Vigoda (2004; pdf) befasst sich mit der Auswahl perfekter Übereinstimmungen aus zweiteiligen Graphen.

In beiden Papieren werden Markov-Ketten schnell gemischt, sodass die Proben nur annähernd gleichförmig sind. Ich stelle mir vor, dass eine einheitliche Probenahme schwierig ist.

Yuval Filmus
quelle

Wenn Sie davon ausgehen, dass Ihr Diagramm planar ist, gibt es ein polynomielles Zeitverfahren für dieses Stichprobenproblem.

Erstens ist das Problem des Zählens der Anzahl perfekter Übereinstimmungen in P für planare Graphen. ( https://en.wikipedia.org/wiki/FKT_algorithm ) (Eine gute Darstellung dieser Tatsache findet sich im ersten Kapitel von Jerrums Buch über Zählen, Abtasten und Integrieren.)

nächstes für jede Kante $e$ von $G$ die Anzahl der perfekten Übereinstimmungen von $G \setminus e$ . Dies lässt sich in die Wahrscheinlichkeit umwandeln, dass eine einheitliche perfekte Übereinstimmung $e$ - nur durch die Anzahl der perfekten Übereinstimmungen in $G$ dividieren enthält . Abtasten Sie eine Kante entsprechend dieser Wahrscheinlichkeit und fahren Sie induktiv fort.

(Dies macht sich die Tatsache zunutze, dass Matchings eine "selbstreduzierbare" Struktur sind, sodass Zählprobleme und einheitliche Stichprobenprobleme im Wesentlichen gleich sind. Weitere Informationen hierzu finden Sie in JVV "Zufällige Erzeugung kombinatorischer Strukturen aus einer einheitlichen Verteilung" Perspektive.)

Ein einfacher Beweis, dass dies die richtige Verteilung ergibt:

Lassen $c(H)$ zeigt die Anzahl der bestellten perfekt passende in einem Graphen $H$ , als geordnete Sequenzen. (Das ist $n!$ Mal die Anzahl ungeordneter perfekter Übereinstimmungen, $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
quelle