\( \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\poly}{\textnormal{poly}} \newcommand{\polylog}{\textnormal{polylog}} \newcommand{\sign}{\textnormal{sign}} \newcommand{\Z}{\mathbb{Z}} \)

Wenn das leichteste perfekte Matching eindeutig ist

Theorem Sei $G = (V,E)$ ein bipartiter Graph und $w: E \rightarrow \{1, ..., W\}$ eine Gewichtung der Kanten. Falls $G$ ein eindeutiges perfektes Matching $M^*$ von kleinstem Gewicht $w^*$ hat, dann können wir $w^*$ und auch $M^*$ parallel in $\poly(n,W)$ Arbeit und $\polylog(n,W)$ Zeit finden.

Beweis. Sei $A = A(G) \in \R^{n \times n}$ die bipartite Adjazenzmatrix, allerdings mit folgenden Einträgen:

\begin{align*} A_{u,v} := \begin{cases} 2^{w(u,v)} & \textnormal{ falls $\{u,v\}$ eine Kante ist,} \\ 0 & \textnormal{ sonst.} \end{cases} \end{align*}

Wir betrachten die Determinante von $A$:

\begin{align} \det(A) & = \sum_{\pi \in S_n} \prod_{u=1}^n \sign (\pi) A_{u, \pi(u)} \label{det-weighted-determinant} \end{align} Zur Erinnerung: wir identifizieren perfekte Matchings in dem vollständigen bipartiten Graphen $(L \cup R, L \times R)$ mit Permutationen $\pi \in S_n$. Die Menge ${\rm PM}(G)$ aller perfekten Matchings in $G$ ist somit eine Menge von Permutationen, und wir erlauben uns, Dinge wie $\sign(M)$ und $\pi \in {\rm PM}(G)$ zu schreiben, wobei wir im ersten Fall $M$ als Permutation lesen und im zweiten Fall $\pi$ als perfektes Matching. Ein Summand in (\ref{det-weighted-determinant}) ist genau dann $0$, wenn das Produkt eine Nicht-Kante $\{u, \pi(u)\} \not \in E$ enthält; die Summanden, die nicht $0$ sind, entsprechen genau den perfekten Matchings von $G$. Es gilt somit \begin{align*} \det(A) & = \sum_{\pi \in {\rm PM}(G)} \prod_{u \in L} \sign(\pi) 2^{w(u, \pi(u))} \\ & = \sum_{M \in {\rm PM}(G)} \prod_{e \in M} \sign(M) 2^{w(e)} \\ & = \sum_{M \in {\rm PM(G)}} \sign(M) 2^{\sum_{e \in M} w(e)} \\ & = \sum_{M \in {\rm PM(G)}} \sign(M) 2^{w(M)} \ . \end{align*}

Da nun $M^*$ ein perfektes Matching von Gewicht $t^*$ ist und nach Annahme alle anderen Matchings Gewicht mindestens $t^*+1$ hat, schreiben wir $\det(A)$ als

\begin{align*} \det(A) & = \sign(M^*) 2^{w(M^*)} + \sum_{M \in {\rm PM} \setminus \{M^*\}} \sign(M) 2^{w(M)} \end{align*}

und sehen, dass der erste Term $\pm 2^{w^*}$ ist und alle weiteren Terme durch $2^{w^*+1}$ teilbar sind. Es gilt daher

Beobachtung $w^*$ ist gleich der höchsten ganzen Zahl $w$, die $\det(A)$ teilt.

Wir können also $w^*$ berechnen, indem wir $\det(A)$ berechnen und dann bestimmen, was die höchste Zweierpotenz ist, die $\det(A)$ teilt. Da die Einträge von $\det(A)$ höchstens $2^W$ sind, brauchen sie höchstens $W+1$ Bits, und wir können die Determinante parallel in $\poly(n,W)$ Arbeit und $\polylog(n,W)$ Zeit bestimmen.

Um schließlich $M^*$ selbst zu bestimmen, benutzen wir folgende Beobachtung:

Beobachtung Sei $e = (u,v) \in E$ eine Kante und sei $A_e := A(G - e)$. Es ist also die Matrix, die wir erhalten, wenn wir $A$ nehmen und $A_{u,v} := 0$ setzen. Es gilt: $e \in M^*$ genau dann, wenn $\det(A)$ nicht durch $2^{w^*+1}$ teilbar ist.

Beweis. Wir betrachten

\begin{align} \det(A_e) & = \sum_{\pi \in {\rm PM}(G-e)} \prod_{u \in L} \sign(\pi) 2^{w(u, \pi(u))} \nonumber \\ & = \sum_{M \in {\rm PM(G-e)}} \sign(M) 2^{w(M)} \label{det-A-e} \end{align}

Wenn nun $e \in M^*$ ist, dann ist $M^* \not \in {\rm PM}(G-e)$; jedes $M \in {\rm PM}(G)$ ist in ${\rm PM}(G) \setminus \{M^*\}$ und hat somit Gewicht mindestens $w^*+1$; es ist also jeder Summand von (\ref{det-A-e}) durch $2^{w^*+1}$ teilbar. Wenn jedoch $e \not \in M^*$ ist, so ist $M^* \in {\rm PM}(G-e)$; die Summe (\ref{det-A-e}) hat also genau einen Term $\pm 2^{w^*}$, und alle anderen sind durch $2^{w^*+1}$ teilbar. \(\square\)

Wir wenden nun parallel auf jede Kante $e \in E$ an, berechnen (parallel) die Determinante $\det(A_e)$ und wissen nun, ob $e \in M^*$ gilt; in anderen Worten: wir kennen $M^*$. Die Gesamtarbeit ist ungefähr $|E|$ mal die Arbeit, die für die Berechnung einer Determinante einer $n \times n$-Matrix mit $W$-stelligen ganzzahligen Einträgen nötig ist; die Zeit ist die für die Berechnung einer solcher Determinante, plus $O(\log W)$. \(\square\)

Übungsaufgabe Woher kommt das "plus $O(\log W)$ in der Laufzeit am Ende des obigen Beweises? Zeigen Sie konkret, wie man

  1. Die Matrix $A$ effizient parallel herstellen kann,
  2. arithmetische Operationen wie $+$ und $*$ effizient berechnen kann, also in $\polylog({\rm bitsize}(x))$ Zeit und
  3. man für $\det(A)$ effizient die größte $w$ bestimmen kann, so dass $2^w \ | \ \det(A)$ gilt.

Wie man das leichteste perfekte Matching eindeutig macht

Wir haben nun einen bipartiten Graphen $G = (V,E)$ ohne Kantengewichte. Wir wollen eine Gewichtsfunktion $w : E \rightarrow \N$ finden, so dass folgendes gilt:

  1. wenn $G$ ein perfektes Matching hat, dann gibt es genau ein solches, das $w(M)$ minimiert;
  2. die Gewichte $w(e)$ sind polynomiell in $n$.

Punkt 2 ist wichtig, weil wir ansonsten die gewichtete Adjazenzmatrix $A(G)$ nicht effizient herstellen können: bereits ihre Darstellung hätte superpolynomielle Größe.

Lemma (Isolation Lemma, [Mulmuley, Vazirani, and Vazirani]). Wähle jedes Gewicht $w(e)$ zufällig aus der Menge $\{1, \dots, 2m\}$, unabhängig für jede Kante. Dann ist

\begin{align*} \Pr\left[\textnormal{es gibt ein eindeutiges $M^* \in {\rm PM}(G)$, das $w(M)$ minimiert}\right] \geq \frac{1}{2} \ . \end{align*}

Beweis. Was muss passieren, damit das leichteste perfekte Matching nicht eindeutig ist? Es muss zwei verschiedene perfekte Matchings $M_1, M_2$ geben mit $w(M_1) = w(M_2) = \min \{w(M) \ | \ M \in {\rm PM}(G)\}$. Diese Matchings müssen sich unterscheiden: es muss eine Kante $e \in M_1 \setminus M_2$ geben.

Dies motiviert folgende Definition: Kante $e$ ist schlecht, wenn es zwei perfekte Matchings $M_1$ und $M_2$ mit minimalem Gewicht gibt und $e \in M_1 \setminus M_2$. Wir stellen uns nun zwei Fragen: (1) Wenn die Gewichte wie beschrieben zufällig gewählt werden, mit welcher Wahrscheinlichkeit gibt es dann überhaupt eine schlechte Kante? (2) Mit welcher Wahrscheinlichkeit ist eine spezifische Kante $e$ schlecht? Um Frage (2) zu beantworten, definieren wir

\begin{align*} w^*_{-e} & := \min \{ w(M) \ | \ M \in {\rm PM}(G), e \not \in M\} \ , \\ w^*_{/e }& := \min \{ w(M\setminus \{e\}) \ | \ M \in {\rm PM}(G), e \in M\} \ . \end{align*}

Wir wählen nun die Gewichtsfunktion $w$ in zwei Schritten: in einem ersten wählen wir $w(f)$ für alle $f \in E \setminus \{e\}$; nur das Gewicht von $e$ bleibt noch offen. Dies ist jedoch genug, um $w^*_{-e}$ und $w^*_{/e}$ zu bestimmen. Nun wählen wir in einem weiteren Schritt $w(e)$. Wann kann nun $e$ schlecht sein? Genau dann, wenn es perfekte Matchings $M_1, M_2$ minimalen Gewichts gibt mit $e \in M_1$ und $e \not \in M_2$. Dann gilt aber $w(M_2) = w^*_{-e}$ und $w(M_1) = w(M_1 \setminus \{e\}) + w(e) = w^*_{/e} + w(e)$ und somit

\begin{align} w^*_{-e} = w^*_{/e} + w(e) \ . \label{eqn-what-is-w} \end{align}

Da $w^*_{-e}$ und $w^*_{/e}$ bereits feststehen, kann es nur eine Wahl für $w(e)$ geben, die (\ref{eqn-what-is-w}) erfüllt: nämlich $w^*_{-e} - w^*_{/e}$. Was ist die Wahrscheinlichkeit, dass wir genau diesen Wert für $w(e)$ wählen? Entweder $1/2m$, wenn der Wert sich in \{1,\dots,2m\} befindet, oder $0$, falls nicht. Die Wahrscheinlichkeit, dass $e$ schlecht ist, ist also höchstens $1/2m$. Nun gilt

\begin{align*} \Pr[\textnormal{das perfekte Matching minimalen Gewichts ist nicht eindeutig}] & = \Pr[\textnormal{es gibt eine schlechte Kante}] \\ & = \sum_{e\in E} \Pr[\textnormal{$e$ ist eine schlechte Kante}] \\ & \leq \sum_{e \in E} \frac{1}{2m} = \frac{m}{2m} = \frac{1}{2} \ . \end{align*}

Und somit gilt: mit Wahrscheinlichkeit mindestens $1/2m$ gibt es ein eindeutiges perfektes Matching von geringstem Gewicht. \(\square\)

Beachten Sie, dass wir zu keinem Zeitpunkt verwendet haben, dass es sich bei den Objekten $M$ um perfekte Matchings handelt. Und in der Tat: das Isolationslemma von MVV funktioniert ganz allgemein für Familien von Mengen.

Übungsaufgabe Was geschieht, wenn die Wahl der Gewichtsfunktion im Isolationslemma fehlschlägt und das Minimum von mehreren perfekten Matchings erreicht wird? Welchen Fehler könnte unser Algorithmus dann machen?