dulmage_mendelsohn_decomposition.md

title	documentation_of
Dulmage–Mendelsohn decomposition （DM 分解）	./dulmage_mendelsohn_decomposition.hpp

二部グラフの Dulmage–Mendelsohn 分解（DM 分解）を行う．計算量は $O((N+M)\sqrt{N})$．

概要

左側頂点集合 $V^{+}$, 右側頂点集合 $V^{-}$, 辺集合 $E$ からなる二部グラフ $G=(V^{+},V^{-},E)$ を考える．Dulmage–Mendelsohn 分解とは，この二部グラフの最大マッチングの性質に基づいて，各頂点集合 $V^{+},V^{-}$ を $V^{\pm }=W_0^{\pm }+\cdots +W_{K+1}^{\pm }$ という $(K+2)$ 個の部分集合 $(K\ge 0)$ へ分割するものである．

具体的には，この分割は以下の性質を満たす：

• グラフ $G$ の最大マッチングに採用されうる辺は $W_k^{+}$ と $W_k^{-}$ $(k=0,\dots ,K+1)$ を両端点に持つものに限られる．
• $W_0^{\pm }$ は「$G$ の任意の最大マッチングにおいて $W_0^{+}$ の頂点は必ず使われるが $W_0^{-}$ の各頂点は必ずしも使われるとは限らない」という性質を満たす．$|W^+_0| < |W^-_0|$ または $W_0^{+}=W_0^{-}=\mathrm{\varnothing }$ が成立する．
• $W_k^{\pm }$ $(k=1,\dots ,K)$ は「$G$ の任意の最大マッチングにおいて $W_k^{+}$ と $W_k^{-}$ の各頂点が一対一にマッチングする」という性質を満たす．すなわち $|W_k^{+}|=|W_k^{-}|>0$ が成立する．
• $W_{K+1}^{\pm }$ は「$G$ の任意の最大マッチングにおいて $W_{K+1}^{-}$ の頂点は必ず使われるが $W_{K+1}^{+}$ の各頂点は必ずしも使われるとは限らない」という性質を満たす．$|W^+_{K + 1}| > |W^-_{K + 1}|$ または $W_{K+1}^{+}=W_{K+1}^{-}=\mathrm{\varnothing }$ が成立する．
• 全ての辺 $(u,v)\in E,(u\in V^{+},v\in V^{-})$ について，$u \in W^+_a$, $v\in W_b^{-}$ とすると $a\le b$ を満たす．すなわち，$W^{\pm}_k$ たちは全ての辺を $V^{+}$ から $V^{-}$ への有向辺とみなした状況においてトポロジカル順序でソートされている．

$K$ が最大となる分割方法は実は（トポロジカル順序に従う並べ方の任意性を除いて）一意で，これが $G$ の DM 分解と呼ばれる．

アルゴリズムの概要

• まず，与えられたグラフ $G$ の最大マッチング $M$ を具体的に一つ求める．
• 上記の最大マッチングで使われなかった頂点たちを始点に探索を行い，これらの頂点と交換可能な頂点集合（$M$ で使用されない頂点を使用して別の最大マッチングをとった際に使われなくなりうる頂点集合）を求める．この過程で探索した頂点たちで $W_0^{\pm },W_{K+1}^{\pm }$ が構成される．
• 残る頂点について，各辺 $(u,v)\in E,u\in V^{+},v\in V^{-}$ について有向辺 $u\to v$� を張り，また $M$ でマッチングに使用された辺については逆辺も張る．このグラフ上で強連結成分分解・トポロジカルソートを行い残る $W_k^{\pm }$ たちを構成する．

使用方法

int L, R;
vector<pair<int, int>> edges;

// L: 左側頂点集合サイズ
// R: 右側頂点集合サイズ
// edges: 0 <= u < L, 0 <= v < R を満たす辺 (u, v) からなる
vector<pair<vector<int>, vector<int>>> ret = dulmage_mendelsohn(L, R, edges);

戻り値 ret は必ず（$L = R = 0$ であっても）長さ 2 以上の vector で，特に ret の先頭と最後の要素に関する first, second の各 vector は空である可能性がある．

ret に含まれる各 pair<vector<int>, vector<int>> について，first の第 $i$ 要素が指す $V^{+}$ の頂点と second の第 $i$ 要素が指す $V^{-}$ の頂点の間には必ず辺が存在する（すなわち，この戻り値を元に即座に最大マッチングが復元できる）．

問題例

• No.1615 Double Down - yukicoder
• AtCoder Beginner Contest 223 G - Vertex Deletion 与えられた二部グラフ（木）を DM 分解した上で $W_0^{-}$ と $W_{K+1}^{+}$ のサイズが求められればよい．

リンク

• Dulmage–Mendelsohn分解 (DM分解) - 室田一雄
• 伊理・藤重・大山『講座・数理計画法 7 グラフ・ネットワーク・マトロイド』産業図書 1986.