An Algorithm for Enumerating Maximal Matchings of a Graph

Presentation on theme: "An Algorithm for Enumerating Maximal Matchings of a Graph"— Presentation transcript:

1 An Algorithm for Enumerating Maximal Matchings of a Graph
宇野 毅明 国立情報学研究所・総合研究大学院大学 2002年 9月19日 アルゴリズム研究会

2 問題の定義 ・ 与えられたグラフ G = (V,E ) に対して、 「 G の全ての極大マッチングを、ちょうど一度ずつ出力せよ
（列挙せよ）」 という問題を考える ・ G の辺グラフを G' とすると、上記の問題は G' の極大安定集合を列挙する問題と等価 ・ G の極大安定集合：　築山らのアルゴリズムで、ひとつあたり O(|V||E| ) 時間で列挙できる 　　　　 G' だと O(|E|×|V||E| ) 時間になる

3 極大安定集合列挙 ・ 極大安定集合列挙アルゴリズムは、斬新なアイディアで作られている。
　 ※ 　それまでのアルゴリズムは、分割法とバックトラッキング 　　　　極大安定集合は列挙できない（出力多項式時間では） ・ 95年にAvis・福田が提案した逆探索と同じ探索をしている ・ 00-01年中野により、いくつかのグラフオブジェクトに対し、このアルゴリズムと同じ方法の、効率良い列挙アルゴリズムが提案されている しかし、 問題が基礎的な割には、 出力多項式アルゴリズムの中でも計算量が大きい

4 問題の特殊化 もともとの動機は、 ・ 極大安定集合列挙を速くしたい  でも、それは難しい
　　　でも、それは難しい 　（データ構造を使っても、ならし解析をしても難しい） ・ せめて、特殊ケースだけでも速く解けないか？ 　　（2部グラフでは O(1 ) で列挙できている） ・ では、極大マッチング、という特殊ケースはどうか 　　　O(|E|×|V||E|) でますます遅くなる 極大マッチングの列挙だけでも速くしよう

5 極大マッチングの逆探索 ・ 築山らの列挙法を、極大マッチングに適用
E = { e1,…,em }, Ei = { e1,…,ei } とする グラフ Gi ＝(V, Ei ) の極大マッチング M を i-極大マッチング と呼び、 ( i, M ) と表記する （ 極大安定集合の場合は、 i-極大安定集合を考える） 全ての i-極大マッチングを列挙する、という問題を考える （そして、普通の極大マッチングだけ出力する）

6 親子関係は、 ( 1, {e1} ) を根とする木になる （列挙木）
極大マッチングの親 i-極大マッチング ( i, M ) に対してその親を (i-1)-極大マッチング ( i-1, M' ) で定める。ただし、 1. ei が M に含まれなければ M' = M 2. そうでなければ M' = M ＼ { ei } に極大になるまで、添え字の昇順で枝を加えたもの 　　　　（ 極大安定集合では頂点を加える） ・ だれも、自分の真の先祖にならない ・ 1-極大マッチング ( 1, {e1} ) だけ親を持たない 親子関係は、 ( 1, {e1} ) を根とする木になる　（列挙木）

7 親の作り方（図解） 1. ei が M に含まれなければ M' = M
2. そうでなければ M' = M ＼ { ei } に極大になるまで添え字の昇順で枝を加えたもの 14 13 12

8 列挙木の例 列挙木

9 与えられた親の子供を見つけるアルゴリズムを考える
列挙木を探索 列挙木を（深さ優先）探索し、全ての頂点を訪れれば、すべての i-極大マッチングが列挙できる　　 （ 　逆探索） 木自体をメモリに持つ 　　極大マッチングを 　　　列挙しなければならない 　　指数メモリが必要 ・ 深さ優先探索をするには、 　今訪れている頂点の子供が得られれば十分 与えられた親の子供を見つけるアルゴリズムを考える

10 子供を求める ・ ( 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 ) の子供であれば、必ずどちらかの方法で得られる （極大安定集合の場合も同じ）

11 子供の求め方（図解） 1. ei+1 が M の辺に接するなら M' = M 、 そうでなければ M' = M ∪{ ei+1 }
2. M' = M ∪{ ei+1 } から ei+1 に隣接する枝を取り除いたもの

12 子供を求める計算時間 ・ ( 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|) ）

13 計算量を算定  1～ |E| 極大マッチングの数は、 任意の i-極大マッチングは ( i<|E| なら ) 子供を1人は持つ
1つあたりの計算時間は O(Δ|E|) ※ Δはグラフの最大次数 　　　（極大安定集合の場合は、 O(|V| |E| ) ） O(|V||E|2) よりは速くなった

14 改良 ・ type 2 の子供を短時間で見つける （データ構造による改良） ・ 列挙木の頂点が多くならないよう、工夫する
　　　（データ構造による改良） ・ 列挙木の頂点が多くならないよう、工夫する 　　　（枝の添え字付けの工夫による） O(Δ) まで速くする

15 Type 2 子供を短時間で発見 2. M' = M ∪{ ei+1 } から ei+1 に接する枝を取り除く v ej
　 (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 より小さいものの数 を、アルゴリズムの実行中保持 ej v

16 Type 2 子供を短時間で発見２ ＊ M' = M ∪{ ei+1 } から ei+1 に隣接する枝を取り除く
ei+1 に隣接する M の枝 e の端点 u が、 u に接続する枝で、M＼ { e } の枝に隣接しないもの を持つと、極大にならない　　 （＋α） 　　  A(u) ＝ φ u u

17 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

18 データ構造の更新 A(v)、l(v) のデータは、 M' △ M の枝に隣接する枝についてのみ、変更がある。
・ type2子供に関する再起呼び出し： O(Δ) 時間 ・ 連続する type1子供に関する再起呼び出し： 　　　※ 最初のマッチングに、枝が単調に追加されるだけ 　( 最後のマッチング )＼(最初のマッチング ) の枝に接続する頂点の次数和　＝　O(|E|) 両者とも、高々（出力数）回　：　1つあたり O(|E|) 時間

19 列挙木の頂点数を減少 ・ 枝集合をブロックに分割 ・ ブロックごとに添え字を付ける
※ ブロックは、（隣接する2本の枝bi,b'i） に隣接する枝全部からなる ※ ブロックを逐次的に枝集合から取り除く ※ 後に取り除いたブロックの枝から昇順に添え字を付ける 枝集合 ・・・

20 ブロック１ ブロック 1,2,…,k ：取り除いた順番 ※ ブロックは（隣接する枝bi,b'i ） に隣接する枝全部
ブロック j+1,…,k の極大マッチングに枝を追加してブロック j,…,k の極大マッチングを作ると、高々3本しか追加されない 　 　　1つのブロック内の、連続する type1子供の再帰呼び 　　　　　出しにかかる時間は O(Δ) 枝集合 ・・・ ・・・

21 ブロック２ ブロック 1,2,…,k ：取り除いた順番 ※ ブロックを逐次的に枝集合から取り除く
　　 （bi,b'i） は、後に取り除いたブロック j>i の枝に隣接しない 　　 ブロック j,…,k の極大マッチングに、 （ bi か b'i ） を加えて、 　　　　2つ以上極大マッチングができる 　　 各ブロック内で、必ず1つ以上、type2子供ができる 枝集合 ・・・ ・・・

22 列挙木をパスに分解 データの更新は、列挙木の各枝に対応  各枝での更新時間の総和を求める
　　 　各枝での更新時間の総和を求める ・ 列挙木を、「type2子供の再帰呼び出し」の枝の端点で分割する ※ 分割されてできるパス・枝の 　　総数は、葉の数の2倍以下 　　 　出力数の2倍以下 ・・・

23 各枝・パスの計算時間 ・ 「type2子供の再帰呼び出し」の枝の計算時間は O(Δ) ・ パスは、連続するｔｙpe1子供の再帰呼び出しに対応
　　 長さは高々2ブロック （枝数6Δ以下） 　　 パスでの計算時間は、O(Δ) 出力ひとつあたり O(Δ) 時間となる ・・・

24 まとめ ・ 築山らによる極大安定集合列挙アルゴリズムを極大マッチング列挙問題に焼きなおした  O(Δ|E|)
・ 極大安定集合列挙が速くならないかなあ