randomized | Finite Playground

首先, FOCS ’11 的 accepted paper list 出來(好幾天)了. 有 pdf 的版本在此. 今年有許多圖論演算法的論文在其中, 很多令人振奮的好結果!

今天想要來講一篇新出爐的, 一個令人驚訝的圖論演算法結果! 我們都知道所謂的 Maximum matching 問題: 給定一張圖, 求上面最大的 matching 的大小. 這個問題在 bipartite graph 上有 Hopcroft-Karp 利用 augmenting path 的 $O(m\sqrt{n})$ 演算法. 這被 Micali-Vazirani 推廣到了 general graph 上, 改進了標準的 Edmonds 開花演算法. 在這之後 Mucha-Sankowski 利用 Gaussian Elimination 及矩陣相乘作到了 randomized $O(n^\omega)$ time.

前兩天, 來自印度資訊科技學院的 Jindal, Kochar 和 Pal 在 Arxiv 上公布了這篇 Maximum Matchings via Glauber Dynamics, 宣稱他們將 maximum matching in general graphs 改進到了 randomized $O(m\log^2 n)$ time, 是第一個 near linear-time 的演算法! 使用的技巧是最近正夯的 Glauber Dynamics, 分析稍微複雜, 但演算法卻是簡單的驚人!

RandMatching(G), G 為 n-node m-edge graph.
1. 令 $M_0$ 為任意 matching. 令 $p = 2^m$ .
2. 執行底下迴圈 $k=10m \log n$ 次, 迴圈參數為 $i$ :
　　2.1 隨機選取一個邊 $e$ .
　　2.2 令 $M'$ 有 $\frac{p}{1+p}$ 的機率是 $M_i \cup \{e\}$ , 有 $\frac{1}{1+p}$ 的機率是 $M_i \setminus \{e\}$ .
　　2.3 假如 $M'$ 是個 matching, 則令 $M_{i+1} = M'$ ; 不然就還是讓 $M_{i+1} = M_i$ .
3. 輸出 $M_k$ , 程式結束.

簡單來說, 根本就是隨便亂選邊, 然後隨機加進去或是拿掉, 然後作了夠多次之後就宣稱輸出的結果有很大的可能性就是一個 maximum matching!! 實在是太不可思議了… 對隨機演算法或是圖論演算法有興趣的人, 這是個必看的結果!

這段時間在學習一個好用的技巧 – Isolation Lemma. 當我們需要在一個圖中找到特定的結構 (例如一個 perfect matching), 有時直接去找不是那麼容易; 藉由孤立 (isolation) 出某一個特定的 minimum weighted matching, 我們就能很快的找到它. 最有名的使用就是在 [MVV87] 中 Mulmuley, Vazirani 和 Vazirani (你沒看錯) 藉由證明了最初 Isolation Lemma 的雛形而得到的 perfect matching $\mathsf{NC}$ (平行) 演算法.

在此我們介紹兩種不同的改良版: 一種是後來被 [RA00] 使用, Reinhardt 和 Allender 證明了 $\mathsf{NL/poly} = \mathsf{UL/poly}$ ; 此種方法的特點是得到的 bound 很好, 但是是非建構式的. 而另一種類似 hash 的方式則是被 [CRS93] 使用, 改進了當初 [MVV87] 的演算法而得的 $\mathsf{NC^2}$ perfect matching 演算法; 後面這種方法 weight 是建構式的, 可以直覺的看出為何它能夠把所有東西分開, 但是要用到少許的 randomization. (嚴格來說, 我們真正要使用第一種方式時, 還是有 randomized 的精神在裡頭.)

—

首先我們來看第一個形式的 Isolation Lemma.

Theorem 1. 令 $U$ 為一大小為 $n$ 的集合, 而 $\mathcal{F}_1, \ldots, \mathcal{F}_m$ 為一族非空集合, 其中每一 $\mathcal{F}_i$ 為 $U$ 的子集所形成的集合. 令 $d$ 為重量的上限, 而 $W$ 為所有重量不超過 $d$ 的重量函數 $w: U \rightarrow [d]^n$ 形成的集合. 若我們給定一參數 $0 < \alpha < 1$ 使得 $\alpha > mn/d$ , 則至少有 $(1-\alpha)|W|$ 的重量函數會使得每個 $\mathcal{F}_1, \ldots, \mathcal{F}_m$ 中正好都只有一個最小重量的 $U$ 子集.

看起來很複雜. 我們令 $m=1$ , $d=2n$ 和 $\alpha = 1/2$ 來觀察這個定理看看.

Theorem 1′. 令 $U$ 為一大小為 $n$ 的集合, 而 $\mathcal{F}$ 為一非空集合, $\mathcal{F}$ 中每一元素為 $U$ 的子集. 均勻獨立的在 $U$ 上隨機給定 $[2n]$ 內的重量. 則至少有 $1/2$ 的機率會使得 $\mathcal{F}$ 中正好只有一個最小重量的 $U$ 子集.

這樣就好懂多了; 藉由隨機給定一些不大的重量, 很容易能夠使得 $\mathcal{F}$ 中有個最小元素被孤立出來. 如果不要限制重量的大小, 這其實不是很困難; 只要對 $U$ 中的元素 $u_1, \ldots, u_n$ 分別給予重量 $2^1, \ldots, 2^n$ 就行了. 不難根據二進位表示看出 $U$ 中的元素都會有不同的重量. 重點在於, 這樣的重量是指數成長的, 而多數演算法的應用只能限制在多項式成長率下. 這時藉由一點點的隨機性, 就能夠達成這樣的目標, 這是 Isolation Lemma 的厲害之處!

來看一個實際的例子好了. 在 [RA00] 的證明當中, 他們用 Isolation Lemma 孤立出圖中某兩點之間的某條路徑. 因為對任意圖來說兩點間的路徑最多會有 exponential 那麼多, 所以我們需要借助 Isolation Lemma.

令 $[p]$ 為圖中的點集, $U$ 為圖中的邊集, $\mathcal{F}_i$ 為點 $1$ 到點 $i$ 所有路徑的集合. (注意我們將路徑視為邊集的子集.) 因為 $|U| = n = p(p-1)$ (有向邊), 我們令 $m=p$ , $\alpha = 1/2$ , $d=2p^3 > mn/\alpha$ . 因此根據 Theorem 1, 我們可以證明底下的推論:

Corollary. 令 $G$ 為一 $p$ 點有向圖, 而 $W$ 為所有重量函數 $w: E(G) \rightarrow [2p^3]^n$ 形成的集合. 則至少有 $|W|/2$ 的重量函數會使得對於所有 $i$ , 點 $1$ 到點 $i$ 的最小重量路徑是唯一的.

為什麼需要這麼多的重量函數呢? 因為我們可以藉此證出更厲害的推論:

Corollary. 令 $W$ 為所有重量函數 $w: E(G) \rightarrow [2p^3]^n$ 形成的集合. 則存在 $w_1, \ldots, w_{p^2} \in W$ 個重量函數會使得對於所有 $p$ 點有向圖 $G$ , 一定有一個 $w_k$ 使得在 $G$ 種任意點 $1$ 到點 $i$ 的最小重量路徑是唯一的.

Proof. 對任意一張圖, $p^2$ 個重量函數都無法估立出最短路徑的機率是 $2^{-p^2}$ . 而 $p$ 個點的有向圖共有 $2^n = 2^{p(p-1)}$ 個, 因此 $p^2$ 個重量函數都無法孤立出某一張 $p$ 點有向圖的最短路徑的機率是

$2^{-p^2} \cdot s^{p(p-1)} < 1$ ,

因此存在某個重量函數不管什麼樣的 $p$ 點有向圖都能夠孤立出其最短路徑. $\Box$

注意後面這個推論的重點: 那 $p^2$ 個重量函數是對所有 $p$ 點的有向圖都適用的, 因此我們可以把這些重量函數事先寫進程式當中, 每當輸入一個圖我們就拿其中一個重量函數來孤立出最短路徑. 如果不使用這種方式, 我們就要在程式執行過程中隨機的產生一些重量函數, 給定了一個圖, 我們需要

$n\log p = O(p^2 \log p)$

個 random bits 來產生一組重量函數.

—

接下來我們來看第二種方法.

前面提到如果不限制重量的大小, 只要對 $U$ 中的元素給予重量 $2^1, \ldots, 2^n$ 就好了. 第二個方法利用中國剩餘定理很輕易的將重量作一些改變而壓在多項式大小, 因此這樣的方法式建構式的. 我們回到只有一個 $\mathcal{F}$ 的狀況, 這次我們利用 $\mathcal{F}$ 內子集的數量來減少 random bits 的使用.

Theorem 2. 令 $U$ 為一大小為 $n$ 的集合, 而 $\mathcal{F}$ 為一非空集合, $\mathcal{F}$ 中每一元素為 $U$ 的子集. 存在一種使用 $O(\log|F| + \log n)$ 個 random bits 的方式在 $U$ 上給定 $[n^7]$ 內的重量, 使得至少有 $1/4$ 的機率會使得 $\mathcal{F}$ 中正好只有一個最小重量的 $U$ 子集.

最糟糕的狀況下 $|F| = 2^n$ , 因此使用的 random bits 會是 $O(n + \log n)$ , 比前一種方法好; 當 $|F|$ 更小的時候 (如|F|是多項式大小), 我們甚至只需要至多$latex O(\log n)$ bits 就夠了. 完整的證明請見 [CRS93]. 不過事實上如果 $|F|$ 只有多項式大小, 我們其實可以連 random 都不要用! 這在 [PTV10] 裡被拿來用以證明 $\mathsf{RFewL} \subseteq \mathsf{UL}$ , 管它這兩個莫名其妙的東西是什麼.

Theorem 2′. 令 $U$ 為一大小為 $n$ 的集合, 而 $\mathcal{F}$ 中有至多 $f(n) = O(n^c)$ 個 $U$ 的子集 $S_1, \ldots, S_{f(n)}$ . 存在一種在 $U$ 上給定多項式大小的重量, 使得 $\mathcal{F}$ 中正好只有一個最小重量的 $U$ 子集.

Proof. 首先我們給 $U$ 中的每個元素 $u_i$ 重量 $2^i$ . 然後我們來看底下這個多項式:

$\Delta = \prod_{1 \leq i < j \leq f(n)} (w(S_i) - w(S_j))$ ,

這個多項式的特色就是: 當重量函數 $w$ 能讓所有 $\mathcal{F}$ 中的元素重量都不一樣時, 這個判別式 $\Delta$ 就會不為零. $\Delta$ 值的範圍會是 $\delta = (2^{n+1})^{f^2(n)}$ . 因此我們選出從2開始的 $s$ 個質數 $p_1, \ldots, p_s$ , 使得它們相乘超過 $\delta = (2^{n+1})^{f^2(n)}$ . 換句話說,

$\Delta \neq 0 \mod \prod_{i=1}^s p_i$ .

根據質數定理,

$\log \prod_{i = 1}^s p_i = s + o(s) > \log \delta = (n+1)f^2(n)$ ,

當 $f(n) = O(n^c)$ 時我們只要有 $s = n^{2c+1}$ 就夠了. 這時中國剩餘定理告訴我們, 因為 $\Delta \neq 0 \mod \prod_{i=1}^s p_i$ , 所以一定有一個 $p_i$ 使得 $\Delta \neq 0 \mod p_i$ . 最後我們只要令新的重量函數為 $w^*(S) = w(S) \mod p_i$ 就行了, 根據對質數大小的估計,

$p_i \leq p_s \leq s\log s \leq n^{2c+2}$ ,

因此這個重量函數只有多項式的大小而已. 因為 $\Delta \neq 0 \mod p_i$ , 所有 $\mathcal{F}$ 中的元素重量都不一樣, 滿足我們對定理的需求. $\Box$

最後有一些後記. Isolation Lemma 使用上需要 randomized, 因為 $\mathcal{F}$ 在最糟的狀況下會有 $2^n$ 個元素, 因此完全的 derandomized 是不可能的. 不過針對 $\mathcal{F}$ 的特性 (例如前面舉的最短路徑的例子), 有些人致力於 derandomize 相關的結果, 也有不少成果. 希望未來能看到 Isolation Lemma 更多的應用!

References.
[MVV87] Matching is as easy as matrix inversion. K. Mulmuley, U. Vazirani and V. Vazirani.
[CRS93] Randomness-optimal unique element isolation, with applications to perfect matching and related problems. S. Chari, P. Rohatgi and A. Srinivasan.
[RA00] Making nondeterminism unambiguous. K. Reinhardt and E. Allender.
[PTV10] On the power of unambiguity in logspace. A. pavan, R. Tewari and N. V. Vinodchandran.

Finite Playground

To verify is human; to prove, divine.

Tag Archives: randomized

Maximum matching in general graphs

Isolation Lemma