一般グラフの最小重み完全matching
概要
奇cycleを含む一般グラフで全頂点をpairにし、weighted blossomまたは重み付きTutte多項式の最小次数からperfect matchingの重みを最小化する。
考え方
二部matchingと異なり、一般グラフでは奇閉路が交互路探索を妨げる。weighted blossomは奇閉路の縮約と奇集合を含む双対制約を扱う。この単元では、非負整数重みが小さく、対応そのものより最小重みが欲しい場合に使える代数的な手順を導く。
掃き出しの更新は線形方程式・rank、有限体上の除算は法上の四則演算・高速累乗・逆元、非零多項式を乱数で評価する誤り上界は乱択の成功条件と誤り確率で確認する。以下では、それらを行列式の最小次数を読む手順へ組み合わせる。
重みをTutte行列の次数へ写す
頂点数Vが偶数の単純無向グラフで、各辺e={i,j}に非負整数重みw_eを与える。自己ループはpairを作れず、多重辺は各頂点対の最小重みの辺だけを残せばよい。まず辺ごとに独立な形式変数z_eを置き、i<jの辺にはB_ij=z_e y^w_e、B_ji=−z_e y^w_eを置く。対角成分と非辺は0。符号は同じ無向辺の変数に対して逆向きに付ける。
P(y)=det Bを展開すると、各置換の項は頂点を覆う有向cycleの集合に対応する。奇cycleを反転した項は符号が逆なので相殺する。残る偶cycleは辺を交互に選ぶと二通りのpairingになり、軽い方の重みはそのcycleの全辺重みの半分以下である。従って次数dの項から重みd/2以下の完全matchingを作れるため、最小重みをOPTとするとd≥2OPTである。
逆に最適matchingの各辺を往復する2-cycleの置換は、次数2OPT、単項式∏_{e∈M}z_e²を生む。この単項式を作る置換は一意なので、形式変数の段階では相殺されない。よってPの最小非零次数はちょうど2OPTとなる。完全matchingがなければ、偶cycleで全頂点を覆う項も存在せずPは恒等的に0である。
例えば4頂点で辺12と34の重みが各1、辺13と24の重みが各3、他の辺がないなら、P(y)=(z_12 z_34 y²−z_13 z_24 y⁶)²となる。最小次数4を2で割り、最小重み2を得る。一点y=1の行列式だけでは、存在判定はできてもこの最小次数を読めない。
乱数代入と係数の復元
十分大きい奇素数pを選び、各z_eにF_pから独立に選んだ乱数r_eを代入する。以降はこの同じ乱数の組を固定して、yだけを変える。最大辺重みをWとすると、行列式の各項はV個の成分の積なので次数上限はD=WVである。
- p>Dを満たす法で、y=0,1,…,Dに対して数値行列を作り、行列式f_jを求める。掃き出し法では非零pivotを探し、行交換で符号を反転し、pivotの積を記録する。pivotが見つからなければその点の行列式は0である。
- 相異なるD+1点からP(y)を補間する。Q(y)=∏_{j=0}^D(y−j)とすれば、P(y)=Σ_{j=0}^D f_j Q(y)/((y−j)Q'(j))。Q'(j)=∏_{k≠j}(j−k)は非零なので除算できる。Qを一度作り、各線形因子で割った係数を足せば、全係数をO(D²)体演算で復元できる。
- 低次から最初の非零係数の次数dを探し、d/2を最小重みとして返す。全係数0なら完全matchingなしと判定する。
最小次数の係数はr_eについて総次数V以下の非零多項式である。Schwartz–Zippelにより、それが偶然0になる確率は高々V/p。乱数代入で本来0の低次係数が非零になることはないため、誤りは最小重みの過大評価または存在の見落としとなる。独立な乱数でt回繰り返し、非零結果の最小値を採れば誤り確率は高々(V/p)^t。行列が一つの評価点で特異になること自体は失敗ではなく、補間に使う正しい0の値である。
成立条件と計算量
行列式をD+1回計算する費用はO((D+1)V³)、上の単純な補間はO(D²)、領域はO(V²+D)。W≥1では行列式部分がO(WV⁴)となり、W=O(V²)の範囲なら単純補間を含む全体もO(WV⁴)。ABC412 Gの0・1重みならO(V⁴)、全辺重み0なら一回の行列式計算O(V³)で足りる。この算法は重みのbit数ではなく値Wに依存する。
補間を高速化するには、NTTの根・長さ条件を満たすL>Dを選び、原始L乗根ωの各冪で行列式を評価して逆NTTで係数を戻してもよい。費用はO(LV³+L log L)となる。ここでも、全評価点で辺ごとの乱数を固定する。
大きい整数重みでは次数上限が大きく、実数重みでは整数次数を割り当てられない。重みの値に依存しないO(V³)の算法を使いたい場合や、辺集合を復元したい場合は、対応するweighted blossom実装の仕様を確認する。本節の代数的手順が直接返すのは最小重みであり、辺集合の復元は別の処理である。
負の整数重みは全辺に同じ定数Cを足して非負にできる。完全matchingは必ずV/2辺なので、得た最小重みからCV/2を引けば元へ戻せる。ただし変換後の最大重みが計算量に入る。Vが奇数なら完全matchingは存在せず、偶数でも存在は保証されない。
問題一覧
- ABC412 G「Degree Harmony」 公式問題
技能・出典
主題: 一般グラフの最小重み完全matching(一般グラフの最小重み完全matchingをweighted blossomまたは重み付きTutte多項式へ帰着し、存在判定だけでなく最小重みまで求められる。)。主タグ: 一般グラフの最小重み完全matching
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 赤色(2800以上)。奇cycleのblossom縮約またはTutte多項式を使う一般matchingの理論を学ぶ。
対象色の読み方は本書の読み方を参照してください。
概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-min-weight-general-perfect-matching
一般グラフの最小重み完全matching
習得する技能
- 一般グラフの最小重み完全matchingをweighted blossomまたは重み付きTutte多項式へ帰着し、存在判定だけでなく最小重みまで求められる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 二部matching・Hall・Kőnig、線形方程式・rank(後の章)、法上の四則演算・高速累乗・逆元(後の章)、乱択の成功条件と誤り確率を設計する。
このUnitを直接前提とする単元: なし。
二部matchingでは表せないpairing模型を作った後、奇cycleを扱うweighted blossomまたは重み付きTutte多項式で最小重みまで求める。
このUnitでは扱わないもの
- 一般グラフの最小重み完全matchingの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。