An Algorithm for Enumerating
Maximal Matchings of a Graph
宇野 毅明
国立情報学研究所・総合研究大学院大学
2002年 9月19日 アルゴリズム研究会
問題の定義
・ 与えられたグラフ G = (V,E ) に対して、
「 G の全ての極大マッチングを、ちょうど一度ずつ出力せよ
（列挙せよ）」
という問題を考える
・ G の辺グラフを G' とすると、上記の問題は G' の極大安定集
合を列挙する問題と等価
・ G の極大安定集合： 築山らのアルゴリズムで、ひとつあたり
O(|V||E| ) 時間で列挙できる
 G' だと O(|E|×|V||E| ) 時間になる
極大安定集合列挙
・ 極大安定集合列挙アルゴリズムは、斬新なアイディアで作られ
ている。
※ それまでのアルゴリズムは、分割法とバックトラッキング
極大安定集合は列挙できない（出力多項式時間では）
・ 95年にAvis・福田が提案した逆探索と同じ探索をしている
・ 00-01年中野により、いくつかのグラフオブジェクトに対し、この
アルゴリズムと同じ方法の、効率良い列挙アルゴリズムが提
案されている
しかし、
問題が基礎的な割には、
出力多項式アルゴリズムの中でも計算量が大きい
問題の特殊化
もともとの動機は、
・ 極大安定集合列挙を速くしたい
 でも、それは難しい
（データ構造を使っても、ならし解析をしても難しい）
・ せめて、特殊ケースだけでも速く解けないか？
（2部グラフでは O(1 ) で列挙できている）
・ では、極大マッチング、という特殊ケースはどうか
 O(|E|×|V||E|) でますます遅くなる
極大マッチングの列挙だけでも速くしよう
極大マッチングの逆探索
・ 築山らの列挙法を、極大マッチングに適用
E = { e1,…,em }, Ei = { e1,…,ei } とする
グラフ Gi ＝(V, Ei ) の極大マッチング M を i-極大マッチング
と呼び、 ( i, M ) と表記する
全ての i-極大マッチングを列挙する、という問題を考える
（そして、普通の極大マッチングだけ出力する）
（ 極大安定集合の場合は、 i-極大安定集合を考える）
極大マッチングの親
i-極大マッチング ( i, M ) に対してその親を
(i-1)-極大マッチング ( i-1, M' ) で定める。ただし、
1. ei が M に含まれなければ M' = M
2. そうでなければ M' = M ＼ { ei } に極大になるまで、添え
字の昇順で枝を加えたもの
（ 極大安定集合では頂点を加える）
・ だれも、自分の真の先祖にならない
・ 1-極大マッチング ( 1, {e1} ) だけ親を持たない
親子関係は、 ( 1, {e1} ) を根とする木になる （列挙木）
親の作り方（図解）
1. ei が M に含まれなければ M' = M
2. そうでなければ M' = M ＼ { ei } に極大になるまで添え
字の昇順で枝を加えたもの
14
13
12
列挙木の例
列挙木
列挙木を探索
列挙木を（深さ優先）探索し、全ての頂点を訪れれば、すべ
ての i-極大マッチングが列挙できる
（  逆探索）
木自体をメモリに持つ
 極大マッチングを
列挙しなければならない
 指数メモリが必要
・ 深さ優先探索をするには、
今訪れている頂点の子供が得られれば十分
与えられた親の子供を見つけるアルゴリズムを考える
子供を求める
・ ( i, M ) に対して
1. ei+1 が M の辺に隣接する： M' = M 、隣接しない： M' = M
∪{ei+1}
 ( i+1, M' ) は ( i, M ) の子供になる
( type1 )
（ type 1 の子供は必ず存在する ）
2. M' = M ∪{ ei+1 } から ei+1 に隣接する枝を取り除いたもの
 ( i+1, M' ) は ( i, M ) の子供になりうる ( type2 )
・ ( i+1, M' ) が ( i, M ) の子供であれば、必ずどちらかの方法で得
られる
（極大安定集合の場合も同じ）
子供の求め方（図解）
1. ei+1 が M の辺に接するなら M' = M 、
そうでなければ M' = M ∪{ ei+1 }
2. M' = M ∪{ ei+1 } から ei+1 に隣接する枝を取り除いたもの
子供を求める計算時間
・ ( i, M ) に対して
type 1 M' = M か M' = M ∪{ ei+1 }
type 2 M' = M ∪{ ei+1 } から ei+1 に隣接する枝を取り除く
 O(1) 時間で得られる
( i+1, M' ) が ( i, M ) の子供であるかどうかのチェック
 O(Δ)
※ Δはグラフの最大次数
（極大安定集合の場合は、 O(|V|)，O(|E|) ）
計算量を算定
任意の i-極大マッチングは ( i<|E| なら ) 子供を1人は持つ
 1～ |E| 極大マッチングの数は、
高々 （極大マッチングの数） × |E|
1つあたりの計算時間は O(Δ|E|)
※ Δはグラフの最大次数
（極大安定集合の場合は、 O(|V| |E| ) ）
O(|V||E|2) よりは速くなった
改良
・ type 2 の子供を短時間で見つける
（データ構造による改良）
・ 列挙木の頂点が多くならないよう、工夫する
（枝の添え字付けの工夫による）
O(Δ) まで速くする
Type 2 子供を短時間で発見
2. M' = M ∪{ ei+1 } から ei+1 に接する枝を取り除く
ej
v
Type 2 の子供であるためには、
(1) ei+1 に隣接する枝があること  O(1) 時間
(2) M' が極大マッチングであること
(3) M'＼ { ei+1 } に追加するべき枝が M の枝であること
各頂点 v （ と v に接続する M の枝 ej ）に対して、
A(v)：(2) のため：v に接続する枝で、M＼ { ej } の枝に隣接しないもの
l(v)： (3) のため： A(v) の枝で、添え字が j より小さいものの数
を、アルゴリズムの実行中保持
Type 2 子供を短時間で発見２
＊ M' = M ∪{ ei+1 } から ei+1 に隣接する枝を取り除く
(2) M' が極大マッチングであること
ei+1 に隣接する M の枝 e の端点 u が、
u に接続する枝で、M＼ { e } の枝に隣接しないもの
を持つと、極大にならない
（＋α）
 A(u) ＝ φ
u
u
Type 2 子供を短時間で発見３
2. M' = M ∪{ ei+1 } から ei+1 に接する枝を取り除く
(3) M'＼ { ei+1 } に追加するべき枝が M の枝であること
ei+1 の端点 u に隣接する M の枝 ej が、
M'＼ { ei+1 } の枝に隣接しない枝の中で、最小添え字
（＋α）
 v に接続する M＼ {ej } の枝に隣接しない枝で、
添え字が j より小さいものの数 ＝ 0  l(u) ＝ 0
u
u
データ構造の更新
A(v)、l(v) のデータは、 M' △ M の枝に隣接する枝についての
み、変更がある。
M' △ M の枝に接続する頂点の次数和の時間
・ type2子供に関する再起呼び出し： O(Δ) 時間
・ 連続する type1子供に関する再起呼び出し：
※ 最初のマッチングに、枝が単調に追加されるだけ
( 最後のマッチング )＼(最初のマッチング ) の枝に接続する頂
点の次数和 ＝ O(|E|)
両者とも、高々（出力数）回 ： 1つあたり O(|E|) 時間
列挙木の頂点数を減少
・ 枝集合をブロックに分割
・ ブロックごとに添え字を付ける
※ ブロックは、（隣接する2本の枝bi,b'i） に隣接する枝全部からなる
※ ブロックを逐次的に枝集合から取り除く
※ 後に取り除いたブロックの枝から昇順に添え字を付ける
枝集合
・・・
ブロック１
ブロック 1,2,…,k ：取り除いた順番
※ ブロックは（隣接する枝bi,b'i ） に隣接する枝全部
ブロック j+1,…,k の極大マッチングに枝を追加してブロック j,…,k
の極大マッチングを作ると、高々3本しか追加されない

1つのブロック内の、連続する type1子供の再帰呼び
出しにかかる時間は O(Δ)
枝集合
・・・
・・・
ブロック２
ブロック 1,2,…,k ：取り除いた順番
※ ブロックを逐次的に枝集合から取り除く
 （bi,b'i） は、後に取り除いたブロック j>i の枝に隣接しない
 ブロック j,…,k の極大マッチングに、 （ bi か b'i ） を加えて、
2つ以上極大マッチングができる
 各ブロック内で、必ず1つ以上、type2子供ができる
枝集合
・・・
・・・
列挙木をパスに分解
データの更新は、列挙木の各枝に対応
 各枝での更新時間の総和を求める
・ 列挙木を、「type2子供の再帰呼び出し」の枝の端点で分割する
※ 分割されてできるパス・枝の
総数は、葉の数の2倍以下
 出力数の2倍以下
・・・
各枝・パスの計算時間
・ 「type2子供の再帰呼び出し」の枝の計算時間は O(Δ)
・ パスは、連続するｔｙpe1子供の再帰呼び出しに対応
 長さは高々2ブロック （枝数6Δ以下）
 パスでの計算時間は、O(Δ)
出力ひとつあたり O(Δ)
時間となる
・・・
まとめ
・ 築山らによる極大安定集合列挙アルゴリズムを極大マッチ
ング列挙問題に焼きなおした
 O(Δ|E|)
・ データ構造の導入をして高速化した
 O(|E|)
・ 添え字の付け方を工夫して高速化した  O(Δ)
・ 極大安定集合列挙が速くならないかなあ

フレネルの公式 マクスウェルの方程式