Finite Playground

To verify is human; to prove, divine.

Leave a comment

Perfect matching equivalence

There are so many things can be written…

Anyway, the following observation is really interesting; details can be found in the book “matching theory” by Lovasz and Plummer.

Consider a general graph G.  An equivalence relationship can be defined on the nodes of the graph as follows: two nodes x and y are equivalent if G-x-y has no perfect matching(!).  


Leave a comment

Dilworth Theorem and equivalence to Konig-Egervary Theorem

Dilworth’s Theorem. If P is a finite poset, then the maximum size of an antichain in P equals the minimum number of chains needed to cover the elements of P.

Proof. Induction on |P|. We separate into two cases.

(a) Some maximum antichain A omits both a maximal element and a minimal element of P. Then neither D[A] or U[A] contains all of P; the maximality of A implies P = D[A] \cup U[A]. Both D[A] and U[A] has width w(P) because they contain A, and they only intersect in A. Apply induction hypothesis on both sets, we obtain k chains covering D[A] and k chains covering U[A]; combining these chains form k chains covering P.

(b) Every maximum antichain of P consists of all maximal elements or all minimal elements. Thus w(P-\{x,y\}) \le k-1 if x is a minimal element and y is a maximal element below x. Apply induction hypothesis on P-\{x,y\} gives us k-1 chains; add chain \{x,y\} to get a covering of P.

Theorem.  Dilworth’s Theorem is equivalent to Konig-Egervary Theorem.

Proof.  Dilworth to Konig-Egervary: View an n-node bipartite graph G as a bipartite poset. The nodes of one part are maximal elements, and nodes of the other part are minimal. Every covering of the poset of size n-k uses k chains of size 2, which is actually a matching. Each antichain of size n-k corresponds to an independent set in G, and the rest of k nodes forms a vertex cover.

Konig-Egervary to Dilworth: Consider an arbitrary poset P of size n. Define a bipartite graph G as follow: For each element x \in P, create two nodes x^- and x^+. The two parts of the graph are \{x^- : x \in P\} and \{x^+ : x \in P\}. The edge set is \{x^- y^+ : x <_P y\}.

Every matching in G yields a chain-covering in P as follow: We start we n chain, each contains a unique element. If x^- y^+ is in the matching then x and y are combined in the same chain. Therefore because each node in G appears in at most on edge of the matching, a matching of k edges forms a covering of n-k chains.

Given a vertex cover R in G of size k, define a corresponding antichain A = \{x \in P : x^-, x^+ \notin R\}; this is indeed an antichain because if there is a relation x <_P y in A then edge x^- y^+ will be presented, and vertex cover R needs to contain at least one of x^-, y^+.

Claim. No minimal vertex cover of G uses both \{x^-,x^+\}, because by transitivity the sets \{z^- : z \in D(x)\} and \{y^+ : y \in U(x)\} induce a complete bipartite subgraph in G. A vertex cover of a complete bipartite graph must use all of one part. Since x^-,x^+ have all the neighbors in these two sets, we can remove one of x^-,x^+ that is not in the right part and decrease the size of the vertex cover.

Thus a minimum vertex cover of size k yields an antichain of size n-k.


Maximum matching in general graphs

首先, 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!! 實在是太不可思議了… 對隨機演算法或是圖論演算法有興趣的人, 這是個必看的結果!