狠狠撸

Faster Matroid Intersection
gasin
Deeparnab Chakrabarty, Yin Tat Lee, Aaron
Sidford, Sahil Singla, Sam Chiu-wai Wong
1

流れ
? 本研究の貢献
? マトロイド交差問題とその周辺知識
? 本研究の貢献（再訪）
? 提案アルゴリズム
2

本論文の貢献
マトロイド交差問題を解く高速なアルゴリズム
を開発した
3

本論文の貢献
を開発した
? 独立集合オラクルを用いての厳密アルゴリズム
? 独立集合オラクルを用いての近似アルゴリズム
? ランクオラクルを用いての厳密アルゴリズム
? ランクオラクルを用いての近似アルゴリズム
色々な問題設定で高速なアルゴリズムを示している
4

本論文の貢献
を開発した
色々な問題設定で高速なアルゴリズムを示している
諸事情（時間、能力、etc.）により今回はこれのみ扱う
5

マトロイド
定義
マトロイドとは有限集合?とその部分集合族? ∈ 2 ?の組(?, ?)で
あって以下の条件を満たすもの
? ? ∈ ?
? ? ? ? ∈ ? ? ? ∈ ?
? ?, ? ∈ ?, ? > ? ? ?? ∈ ?? ?. ?. ? ∪ ? ∈ ?
用語
独立集合 … ?の要素(?の要素は集合）
基 … ?の極大要素（基のサイズは等しい）
6

? 分割マトロイド
? 色付きの点集合が与えられる
? 各色高々1つまで選んでできる点集合を独立集合とする
? 基は各色から1つ選んでできる点集合
? 閉路マトロイド
? グラフ?(?, ?)が与えられる
? 辺集合であって閉路を含まないものを独立集合とする
? ?が連結なら基は全域木
マトロイドの例
7

マトロイドの応用例
? マトロイド(?, ?)とコスト関数?: ? → ?≥0が与えられたとき、
独立集合のうちコスト最大のものが貪欲法で求められる
? 重み付きの色付き点集合が与えられる
? 各色高々1つまで選べるとき重みを最大化せよ
→ 分割マトロイドなので貪欲に解ける（直感的にもok）
? 辺が重みづけられたグラフが与えられる
? 最大全域木を求めよ
→閉路マトロイドなので貪欲に解ける
→少し工夫すると最小全域木も求められる（Kruskal法）
8

マトロイド交差問題
? 辺に色が付けられたグラフが与えられる
1. 各色の辺を高々1つまで選べる
2. 選んだ辺で閉路ができてはいけない
辺数が最大になるように辺を選べ
9

? 辺に色が付けられたグラフが与えられる
1. 各色の辺を高々1つまで選べる
2. 選んだ辺で閉路ができてはいけない
辺数が最大になるように辺を選べ
10
条件1は分割マトロイド
条件2は閉路マトロイド
最大の共通の独立集合は？？

マトロイド(?, ?1)とマトロイド(?, ?2)が与えられたとき?1
と?2どちらにも含まれる?の部分集合（共通独立集合）の
うち最大サイズのものを求めよ
11
? 先ほどの例は分割マトロイドと閉路マトロイドの交差
? 色々なマトロイドを組み合わせることで多くの問題を扱える
? ただし、3つ以上のマトロイドを組み合わせるとNP困難

12
例: 閉路マトロイドと閉路マトロイドのマトロイド交差
?辺数mのグラフが2つある
?辺が互いのグラフで対応している
?辺の集合であってどちらのグラフにも閉路ができないもののう
ち最大のものを求めよ
? ?
? ?
? ?
? ?
? ?
? ?
? ?
? ?
? ?
? ?
? ?
? ?

マトロイド交差の応用例
二部グラフの最大マッチング問題
→ 分割マトロイド同士のマトロイド交差問題として解ける
13
? ?
? ?
? ?
? ?
? ?
1
1,2
2,3,5
3,4
4
5
各頂点に辺のインデックスを持たせる
各頂点について高々1つまで辺が選べる
選べる辺の数の最大化

独立集合オラクル
? マトロイド(?, ?)について、ある?の部分集合?が独立集合かど
うか判定したくなる
? しかし、?のサイズは最大で2 ?にもなり、?を陽には持てない
? ?が独立集合かチェックするオラクルの存在を仮定する
→ 独立集合オラクルは?が独立集合か判定してくれるもの
計算量は一回ごとに?(????)と仮定
14
分割マトロイドの独立集合オラクル
点集合を受け取って、色の重複をチェック
閉路マトロイドの独立集合オラクル
辺集合を受け取って、閉路の有無をチェック

本論文の貢献（再訪）
Edmonds … ? ??2
???? 時間
Cunningham … ?(??1.5 ????)時間
Lee, et al. … ?(?2 ???? + ?3)時間
本論文 … ?(?? ??? ? ? ????)時間
（厳密には?( ?? + ? ?
??? ? ????)時間）
15
重みなし?独立集合オラクル最初の多項式時間
アルゴリズム
State-of-the-art
だった
?は頂点数
?はマトロイド交差のサイズ

基本のアイディア（Edmonds)
? マトロイドM1(?, ?1)とマトロイドM2(?, ?2)について考える
? 共通独立集合A ∈ ?1 ∩ ?2を空集合からスタートして、サイズを1
つずつ大きくしていく
? 交換グラフの上での最短経路問題を解くことで大きくする
? 気持ちとしては二部グラフの最大マッチングを求めるときの増加道に
よるアルゴリズム
16

交換グラフ
? 今持っている共通独立集合をA ∈ ?1 ∩ ?2とする
? ?と?Aの二部グラフに2点付け加えたグラフを考える
17
? ?A
?
?
?から?への最短経路上には?Aの点が?の点よりも1つ多く存在する
最短経路上の?Aの点を?に追加し、最短経路上の?の点を?から削除する
新しい?が共通独立集合になるように辺を張る

交換グラフ
18
? ?A
?
?
? ∈ ?A ?. ?. ? + ? ∈ ? ?に
?から辺が伸びている
? ∈ ?A ?. ?. ? + ? ∈ ? ?から
?に辺が伸びている
? ∈ ?A ?. ?. ? + ? ∈ ?1 ∩ ?2なる?が存在したら
? → ? → ?の最短経路が存在するので?を?に追加

交換グラフ
19
? ?A
?
?
?1 ∈ ?A, ?2 ∈ ? ?. ?. ? ? ?2 + ?1 ∈ ? ?に
?1 → ?2の辺が伸びている
?1 ∈ ?A, ?2 ∈ ? ?. ?. ? ? ?2 + ?1 ∈ ? ?に
?2 → ?1の辺が伸びている
?1の独立集合を?2の独立集合
にもなるように要素を1つ削除
?1かつ?2の独立集合を?1の独立
集合になるように要素を1つ追加

交換グラフ
20
? ?A
?
?
気持ち
?1と?2の共通独立集合?からスタート
? ?の独立集合を維持して1要素追加、共通独立集合になるように1要素削除を
繰り返す
1要素追加したときに? ?の独立集合にもなっていたら成功

基本のアイディア（Edmonds)
空集合からスタート
交換グラフ上での最短経路問題を繰り返し解く
? 繰り返しの数 … ?回
? グラフの辺数 …?(??)本
? 構築に?(?? ? ????)時間
? 最短経路問題に?(??)時間
? 全体で?(??2 ? ????)時間
21
?は頂点数
?はマトロイド交差のサイズ

本論文のアイディア1~二分探索~
? マトロイドM(?, ?)と独立集合?があるとする
? 以下のことが可能（詳細は次スライド）
? ? ∈ ?S, ? ? ?について、
? ? ? ? + ?が独立集合であるa ∈ ?を?(log ? ? ????)時間で見つける
? そのような?が存在しない場合?(????)時間で判定する
22
Sに追加したい要素?があるとき、何を?から消せば
独立集合であり続けるか効率よく見つける

本論文のアイディア1~二分探索~
23
?を丸ごと取り除いても独立集合じゃないならだめ
? ? ? + ?が独立集合なら、マトロイドの性質より? ? ? + ? ∈ ?なる? ∈ ?が存在する
（?が独立集合なので?の要素を? ? ? + ?に追加し続けられる）
そのような?の1つを二分探索で見つける

本論文のアイディア2 ~距離の利用~
? 交換グラフ上の?からの距離の単調性(Cunningham)
? Edmondsのアルゴリズムによって得られる交換グラフを ?0, … , ?? とし、
それぞれのグラフ上での距離を?0, … , ? ?とする
? 0 ≤ ? < ? ≤ ?, ? ∈ ?について、?? ?, ? ≤ ?? ?, ? が成り立つ
? 交換グラフ上の?から各頂点への距離は広義単調増加する
? 各頂点について?からの距離を常に保持しておき、更新が必要
な時だけ更新する
? 更新の回数は各頂点につき高々?(?)回
? 全体で?(??)回
24

本論文のアルゴリズム概観
? 以下を繰り返す
? 交換グラフ上の各頂点の?からの距離を以前の情報を用いて更新する
? 距離の単調性
? 二分探索のテクニック
? 交換グラフ上の各頂点について?からの距離がわかっていれば?から逆順
に辿れば? ? ?最短経路が構築できる
? できなければ終了
? 共通独立集合を最短経路で更新する
25

本論文のアルゴリズム概観
? 以下を繰り返す
? 交換グラフ上の各頂点の?からの距離を以前の情報を用いて更新する
? 距離の単調性
? 二分探索のテクニック
? 交換グラフ上の各頂点について?からの距離がわかっていれば?から逆順
に辿れば? ? ?最短経路が構築できる
? できなければ終了
? 共通独立集合を最短経路で更新する
26

? 幅優先探索の要領で距離0から順に構築していく
? ?に到達出来たら打切り
? 距離の偶奇で場合分けして考える
距離の計算
27
? ?A
?
?
?からの距離が偶数 ?からの距離が奇数

距離の計算
? 距離?の頂点集合を??とおく
? ??+1の計算（? + 1は奇数、?? (? ≤ ?)は既に計算済み）
? ??+1の候補の頂点?について考える
? ??から?に辺が伸びているかの判定は?(????)でできる
? 共通独立集合に?を加えるには??の何を消せばよいか
? 辺があったら??+1に?を追加
? 辺が無かったら??+?の候補に?を追加
? ??+1の候補が空になるまで繰り返す
28
各頂点について距離の更新は高々O(2?)回
奇数距離の頂点数は?(?)
全体で?(?? ? ????)時間
候補は距離の下限を意味しており、
初期値は前回の距離の値（単調性）

距離の計算
? ??+1の計算（? + 1は偶数、?? (? ≤ ?)は既に計算済み）
? 初期状態では??+1にはその候補（以前の距離）が入っている
29
?から?への辺を見つける
存在すれば?(log |?| ? ????)時間
存在しなければ?(????)時間
外側のwhile文は?(??)回呼ばれる
内側のwhile文の中には?(?2
)回入る（ ? ≤ ?)
全体で?( ?? + ?2 log ? ? ????)時間

本論文のアルゴリズム
? 交換グラフの距離の更新の仕方を説明した
? 全体で?( ?? + ?2 log ? ? ????)時間
? 交換グラフ上の最短距離検出
? 距離がわかっていれば一回当たり?(? ? ????)時間で検出可能
? 単純な深さ優先探索
? アルゴリズム全体で?( ?? + ?2
log ? ? ????)時間
30

本スライドのまとめ
? マトロイド?マトロイド交差についての説明
? 応用例など
? 重みなし?独立集合オラクルでのマトロイド交差問題の
?( ?? + ?2 log ? ? ????)時間アルゴリズムの紹介
? 距離の単調性を利用した手法
? 二分探索の手法
31

今後やるかもしれないこと
32
下の3つを理解する（本スライドは一番上）
3つ以上のマトロイドの交差について調べる
FPTアルゴリズムが存在するのか、など

狠狠撸

Faster matroid intersection

Recommended

More Related Content

What's hot (20)

Similar to Faster matroid intersection (20)

Faster matroid intersection