Maximum Unweighted Matching Algorithm

個人的メモ

グラフ $G$ が完全マッチングを持つことと $G$ の Tutte 行列の行列式が恒等的に $0$ ではないことの同値性を用いる. $\det$ 計算における置換に注目すると奇閉路(奇数長の巡回置換) の存在する項は逆向きの項と打ち消し合って消え, 偶閉路のみからなる項のみ残りうる. もし偶閉路のみからなる $0$ でない項が残った場合はグラフ $G$ 上で対応する完マを取ることができるので "Tutte 行列の行列式が恒等的に $0$ ではない $\rightarrow$ $G$ は完マを持つ" が成り立つ.
また逆にグラフ $G$ に完マが存在するならそれに対応して Tutte 行列の行列式に偶閉路のみからなる $0$ でない項が存在し, その項は他の項と打ち消し合って消えることはない. よって "$G$ は完マを持つ $\rightarrow$ Tutte 行列の行列式が恒等的に $0$ ではない" も成り立つ.
よって $n$ 次の多変数多項式($\det T$) が恒等的に $0$ であるかどうかを判定できれば良いのだが決定的に行おうとすると効率的に解けないため各変数に乱数を代入し, その結果が $0$ に等しいかどうかで判定する($\mathbb{Z}_p$ 上で行う).
Shwartz-Zippel Lemma より $\det T$ が恒等的に $0$ でないのに上記の計算結果が $0$ になってしまう(完全マッチングを持つのに持たないと判定する)確率は $\O (n / p)$ となり, 例えば $n = 10^2$, $p = 10^9 + 7$ のときは $1$ 度の試行で十分である(不安なら $LOOP$ の値を大きくする).
(注) $G$ の最大マッチングの数は $\mathrm{rank} (T) / 2$ に等しい($\mathrm{rank}$ が $r$ の交代行列は $r \times r$ の正則な主小行列を持つことから言える $\Rightarrow$ 補足 1).

(構築の話)
構築だがグラフが完全マッチングを持つという条件を保ったまま縮小していくことをする. ただし $G$ が完全マッチングを持たない場合は Gaussian elimination を用いて Tutte 行列の中に含まれる $\mathrm{rank} (T) \times \mathrm{rank} (T)$ の正則な主小行列を事前に求めておく. 愚直に全辺についてそれを除いたグラフが完全マッチングを持つかどうかを調べていくと $\O (n^5)$ かかる.
行列 $T$ から $\{ u_1, \ldots, u_k \} \subseteq [n]$ に含まれる添字の行および $\{ v_1, \ldots, v_l \} \subseteq [n]$ に含まれる添字の列を削除したものを $T_{ \langle u_1 \ldots, u_k \rangle , \langle v_1 \ldots, v_l \rangle }$ と書くことにする. $\det T$ を $1$ 行目で余因子展開したものを $\det (T) = \sum_{j=1}^n (-1)^{i+j} T_{1, j} \det (T_{\langle 1 \rangle, \langle j \rangle})$ と表せ, $\det T \neq 0$ なら $T_{1,j} \neq 0$(辺 $(1, j)$ が存在する) で $\det (T_{ \langle 1 \rangle ,\langle j \rangle }) \neq 0$ となるものが存在する.
また $\det (T_{\langle 1 \rangle ,\langle j\rangle }) \neq 0 \Rightarrow \det (T_{ \langle 1,j \rangle ,\langle 1,j \rangle }) \neq 0$ より頂点 $1$ および頂点 $j$ を取り除いた後のグラフは完全マッチングを持つ($\Rightarrow$ 補足 2).
あとは $\det (T_{ \langle 1 \rangle ,\langle j \rangle }) \neq 0$ となるような $j$ をどうやって見つけてくるかだが $(T^{-1})_{i, j} = (-1)^{i+j} \cdot \frac{\det \left( {T_{\langle i \rangle, \langle j \rangle}} \right)}{\det \left( T \right) }$ より, $\det (T_ { \langle 1 \rangle ,\langle j \rangle }) \neq 0 \Leftrightarrow \left( T^{-1} \right) _{1,j} \neq 0$ が得られるので $T$ の逆行列を計算することで $j$ を求めることができる.
これを再帰的に繰り返すことで $\O (n^4)$ で構築することが可能になった(正確には $\O (n^{ω+1})$ time).
ここで逆行列計算を毎回する必要はなく $T^{-1}$ から $\left( T_ { \langle 1,j \rangle ,\langle 1,j \rangle } \right) ^ {-1}$ を $\O \left( n^2 \right)$ 時間で計算することができる.
簡単のため $j = 2$ とする. ここで元の行列 $T$ の行置換や列置換は $T^{-1}$ の行置換および列置換とそのまま対応するので特に一般性を失うことなく議論が可能であることに注意する. $T^{-1}$ を $(2, n-2) \times (2, n-2)$ ブロック行列 と見たとき右下の行列に関する Schur 補行列は $\left( T_ { \langle 1,2 \rangle ,\langle 1, 2 \rangle } \right) ^ {-1}$ と一致する. つまり頂点 $1$ および頂点 $2$ を取り除いた後の Tutte 行列の逆行列は $T^{-1}$ が求まっていると $\O (n^2)$ 時間で構築することができる. つまり全体で $\O (n^3)$ time で計算可能. ちなみにもっと頑張ると $\O (n^ω)$ まで落ちるらしい

以下では交代行列の性質を用いて導かれる本文中の自明でない結果 (補足 1), (補足 2) について証明を雑に記す. (補足 2) の方は参考資料を参照した.
(補足 1)
$\mathrm{rank}$ が $r$ の交代行列 $A \in \mathbb{R}^{n \times n}$ が $r \times r$ の正則な主小行列を持つことを示す. $A$ の固有多項式を考える. すると有名な事実として $\det (xI - A) = \sum_{0 \le k \le n} \left( (-1)^{n-k} \underset{X \subseteq [n], |X| = n - k}{\sum} \det (A_{X, X}) \right) x^k$ が言える (正方行列 $A$ の特性多項式の係数は $A$ の 主小行列式の和を用いて書ける).
交代行列は正規行列であることから対角化可能であり, 固有値の幾何的重複度と代数的重複度が一致するため, 今 $r = \mathrm{rank} A$ から固有多項式の最小の非ゼロ係数項の指数は $n - r$ となる. つまり $\exists X \subseteq [n], |X| = r$ について $\det (A_{X, X}) \neq 0$ が成り立つ.
(補足 2)
$\det (T_{\langle 1 \rangle ,\langle j\rangle }) \neq 0 \Rightarrow \det (T_{ \langle 1,j \rangle ,\langle 1,j \rangle }) \neq 0$ を示す.
初めに以下に証明に用いる交代行列に関するフロベニウスの定理を記す.
$A \in \mathbb{R}^{n \times n}$ を交代行列とし, $\alpha, \beta \subseteq [n]$ を $|\alpha| = |\beta| = \mathrm{rank}(A)$ を満たすインデックスの集合とする. このとき $\det (A_{\alpha, \alpha}) \det (A_{\beta, \beta}) = (-1)^{|\alpha|} \det (A_{\alpha, \beta})^2$ が成り立つ.
これを用いて定理を示す.
まず $j = 2$ として一般性を失わない. $n$ が奇数のとき交代行列の行列式は $0$ となるので $T_{\langle 1 \rangle, \langle 1 \rangle } = 0$ であるが, 仮定より $T_{\langle 1 \rangle, \langle 2 \rangle } \neq 0$ なので $T_{\langle 1 \rangle, \langle 1, 2 \rangle }$ は列フルランクである. よって $\mathrm{rank} \left( T_{\langle 1 \rangle, \langle 1 \rangle } \right)$ は $n-2$ となる. さらに $\beta = \{ 3, \cdots, n \}$ としたとき, $\exists \alpha \subseteq \{ 2, \cdots, n \}, |\alpha | = n - 2$ で $A_{\alpha, \beta}$ が正則となるようなものが存在することも分かる. 最後にフロベニウスの定理より, $\det (A_{\alpha, \beta}) \neq 0 \Rightarrow \det (A_{\beta, \beta}) \neq 0$ が導けるので確かに $\det \left( T_{\langle 1, 2 \rangle, \langle 1, 2 \rangle } \right) \neq 0$ が言える.
(追記) (補足 2) については bimatroid の基の交換定理を用いても証明することが可能です(友人に教えてもらいました).