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 子供を短時間で発見2
* M' = M ∪{ ei+1 } から ei+1 に隣接する枝を取り除く
(2) M' が極大マッチングであること
ei+1 に隣接する M の枝 e の端点 u が、
u に接続する枝で、M\ { e } の枝に隣接しないもの
を持つと、極大にならない
(+α)
 A(u) = φ
u
u
Type 2 子供を短時間で発見3
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
ブロック 1,2,…,k :取り除いた順番
※ ブロックは(隣接する枝bi,b'i ) に隣接する枝全部
ブロック j+1,…,k の極大マッチングに枝を追加してブロック j,…,k
の極大マッチングを作ると、高々3本しか追加されない

1つのブロック内の、連続する type1子供の再帰呼び
出しにかかる時間は O(Δ)
枝集合
・・・
・・・
ブロック2
ブロック 1,2,…,k :取り除いた順番
※ ブロックを逐次的に枝集合から取り除く
 (bi,b'i) は、後に取り除いたブロック j>i の枝に隣接しない
 ブロック j,…,k の極大マッチングに、 ( bi か b'i ) を加えて、
2つ以上極大マッチングができる
 各ブロック内で、必ず1つ以上、type2子供ができる
枝集合
・・・
・・・
列挙木をパスに分解
データの更新は、列挙木の各枝に対応
 各枝での更新時間の総和を求める
・ 列挙木を、「type2子供の再帰呼び出し」の枝の端点で分割する
※ 分割されてできるパス・枝の
総数は、葉の数の2倍以下
 出力数の2倍以下
・・・
各枝・パスの計算時間
・ 「type2子供の再帰呼び出し」の枝の計算時間は O(Δ)
・ パスは、連続するtype1子供の再帰呼び出しに対応
 長さは高々2ブロック (枝数6Δ以下)
 パスでの計算時間は、O(Δ)
出力ひとつあたり O(Δ)
時間となる
・・・
まとめ
・ 築山らによる極大安定集合列挙アルゴリズムを極大マッチ
ング列挙問題に焼きなおした
 O(Δ|E|)
・ データ構造の導入をして高速化した
 O(|E|)
・ 添え字の付け方を工夫して高速化した  O(Δ)
・ 極大安定集合列挙が速くならないかなあ
ダウンロード

M - 国立情報学研究所