Saturday, October 02, 2010

Testing cycle-freeness in bounded-degree graphs and my feelings of randomized algorithms

在圖形性質的 property testing 裡,一般不是使用 adjacency matrix,就是使用 adjacency list 來儲存一個 graph。通常 property testing 這個領域的 papers 裡,使用 adjacency list 來儲存一個 graph 的時候,會再假設 graph 的 maximum degree 至多為 d,也就是說,這樣的 model 是用來處理 bounded-degree graphs。我們可以把儲存一個 graph 的 adjacency list 當成一個 oracle,任何演算法在每個單位時間內只能得知某一個點的第幾個鄰居為哪一個點。


在圖形性質的 property testing 裡,一般不是使用 adjacency matrix,就是使用 adjacency list 來儲存一個 graph。通常 property testing 這個領域的 papers 裡,使用 adjacency list 來儲存一個 graph 的時候,會再假設 graph 的 maximum degree 至多為 d,也就是說,這樣的 model 是用來處理 bounded-degree graphs。我們可以把儲存一個 graph 的 adjacency list 當成一個 oracle,任何演算法在每個單位時間內只能得知某一個點的第幾個鄰居為哪一個點。

先回味一下 property testing 的目標:給定一個 input 與一個參數 epsilon,另外指定一個性質 P,我們必須有「九成的把握」去判斷這個 input 到底是滿足性質 P,還是必須修改當中至少 epsilon 比例的值才能滿足性質 P。我們稱滿足後者的 input 為 epsilon-far from P,講比較口語一點,就是說這個 input 要滿足性質 P 還差得很遠。傳統的演算法 decision 問題,都是問一個 input 是不是滿足某一個性質,是的話就必須 accept,否則就一定得 reject。這就好比隨便抓一個人到你面前,要你判斷這個人是好人還是壞人。而 property testing 把問題的要求放寬了,不僅把 no-instance 改成 epsilon-far instance,而且還允許演算法犯錯,只不過犯錯的機率要很小。就拿前面那個例子來說,隨便抓一個人給你,要你分辨他是善良老百姓還是罪大惡極的凶神惡煞,這當然容易多了,俗話說「相由心生」,可能看到他的臉就可以下判斷了,況且你還被允許可以有判斷錯誤的可能性哩!在這樣的條件下,property testing 要求演算法的執行時間必須非常迅速,甚至不能跟 input size 有關,也就是說,最好是只跟 epsilon, d 有關的「常數」。

我跟 Ling-Ju 與老師在今年九月初到德國的 RWTH Informatik 待了兩週,在那裡和 Peter 討論關於 結合 parameterized algorithms 與 property testing 兩邊的方法來解決問題的可能性。因為 Peter 簡單介紹了前人針對 bounded-degree graphs 的 cycle-freeness 所設計的一個 property testing 演算法,我覺得蠻有趣的,於是硬逼著自己用最快的速度的把頭影片完成 (投影片可按此下載),然後在本週的 group meeting 中向大家報告。這個 property testing 演算法的精神概略如下。

如果一個 graph 沒有 cycle,那它不是 tree 就是 forest。如果是 tree,那麼它的邊數就是點數減一,如果是 forest,那它的邊數就是點數減一再減去 components 的數目。由此可知,一個 cycle-free 的 graph 它的邊數一定不會超過點數。我們可以在 graph 中隨機抽樣一些點,然後讓這些點做「小範圍」的 BFS (Breadth-first search),在 bounded-degree graphs 上的 property testing,這算是蠻典型的做法。如果在 BFS 搜尋中發現了 cycle,那演算法就立刻停止並回傳 reject,因為,因為它不是 cycle-free。如果都沒發現 cycle 呢?接下來就是比較 tricky 的部份了。

在這些隨機抽樣的點所分別進行的 BFS 裡面,我們可以找到一些 graph 中的大區塊和小區塊。是大或小我們可以設一個標準,一個連通的子圖的點數超過這個標準,我們就說它是大區塊,反之就說他是小區塊。如何從剛剛的那些 BFS 結果得知?這倒不難,只要 BFS 還沒走到這個設定的標準大小就停了,表示抽樣的點是處於一個小區塊,才使得 BFS 才使得無法繼續下去。而如果該 BFS 是因為拜訪的點數夠多了才被我們喊卡停下來,那當然就表示這抽樣的點落在一個大區塊裡。假設 input 的 graph 距離 cycle-free 是 epsilon-far,代表它必須移除相當多的邊才會沒有 cycle,那我們稱這些邊叫做「過剩邊」。我們討論以下兩種情況:

  • 一、大部分的過剩邊都落在小區塊中;
  • 二、大部分的過剩邊都落在大區塊中。

第一種情況會在 testing 的第一階段中 (也就是抽樣一些點然後分別實行 BFS) 就會被發現,因為過剩邊多,這些邊上面的點自然也不少 (因為我們討論的 graph 是 bounded-degree),那麼我們隨機抽樣就很容易抓到這些點,然後因為它們落在小區塊中,BFS 不用找很久就可以探索出這個小區塊,並且發現過剩邊,而發現了一條過剩邊,根據過剩邊的定義,就等於我們找到 cycle 囉。

至於第二種情況,就表示我們沒辦法在第一階段中找出 cycle 來,除非我們把 BFS 可以走的範圍加大,但是這麼一來可能會讓演算法的時間複雜度變得太大。沒關係,我們知道大部分的過剩邊都在大區塊中,根據上一段的論述,我們知道這些大區塊裡面的邊數一定會超出點數不少,從這點來下手,我們可以從抽樣的點數和這些點得鄰居數量結果來做判斷。

以上著墨於 epsilon-far 的 input graphs,那麼 cycle-free 的 graphs 又當如何是好?其實,一個 cycle-free 的 graph,只可能在演算法的第二階段裡被 reject,而且是由於抽樣點的邊數和超過這些點太多所造成,不過這發生的機會相當小 (可以經由複雜的機率計算後得知)。

這樣的 property testing 很精妙,仔細推敲後也不難看出它的確蠻複雜的。不像大部分的演算法只在抽樣後直接從結果下判斷,這一個 cycle-freeness testing 演算法拐了好幾個彎,最後還有點旁敲側擊的味道,從抽樣得來的點與邊的比例去判斷一個 graph 是不是沒有 cycle,值得好好玩味一番。

話說最近有學弟跟我說他想做隨機演算法相關的研究,我覺得有幾點事情要先釐清比較好。

  • 一、 Discrete Probability Theory 與 Combinatorial Mathematics 要學過。
  • 二、「隨機演算法」只能說是一種演算法設計的「策略」,所以,你還是得選擇一個「主題」才能進行研究。譬如說,我選擇的 property testing。
  • 三、如果稱我為隨機演算法或 property testing 的專家,坦白說我很心虛。隨機演算法相關的領域和牽涉到的演算法與計算理論層面相當廣,而且不是做隨機演算法,就可以把決定性 (deterministic) 的演算法和知識丟在一邊。就好比一個人說要做一個問題的近似演算法研究,但是他卻不知道該問題已經有多項式時間複雜度的演算法。
  • 四、國內的從事相關研究的人很少,所以你很難得到奧援,做出了結果,你要說服大家你的結果是對的,也要花費一番功夫。
  • 五、你有相當濃厚的興趣嗎?如果走這條路可能無法做出結果,導致你無法畢業,你要走嗎?

雖然多年以來,我好像有一些成果,不過事實上我不足的地方實在太多了。要不是我有著近乎瘋狂的興趣和堅持,我應該早就放棄這條路了。感謝上帝和老師帶領我和指導我,至少這幾年來,我的努力所得到的結果並不是空白。

No comments: