修士論文 要旨

高速行列積による効率的セレクティングアルゴリズム
数理情報学専攻 48-206235
指導教員

1 はじめにセレクティングは, 順序付き有限集合に対して, 整数的矢 知樹
鈴木 大慈 准教授

例である全域木に対しては, 行列木定理による数え上げと同じ計算時間のセレクティングアルゴリズムが知られている [1].

i が入力されたときに i 番目の要素を出力する問題であ

本研究では, 行列式を用いて数え上げが可能であるこり, ランキングは, 入力された集合の要素に対して何番とが知られている離散構造に対するセレクティングア目の要素か答える問題である. この２つの問題はサンプルゴリズム, 特に行列式計算と同じ計算時間のセレクリングとデータ圧縮という非常に重要な問題と密接なティングアルゴリズムを提示する.

関係がある.
サンプリングは与えられた離散分布に従ってインスタンスを生成する重要な問題である. もしもセレクティングが可能であれば, 一様分布を入力することで離散集合上の一様サンプリングが可能となる.

3 主結果
3.1

ナイーブサンプリングKulkarni は, 多項式時間数え上げが可能な離散集合に対して, その離散集合上の一様分布のサンプリングを有限集合 S が与えられたとき, その要素を表現する多項式時間で行うことが出来るアルゴリズムを示した.

ためには少なくとも ⌈log |S|⌉ ビット必要である. ラン

本研究では, 多項式時間数え上げが可能な離散集合に対キングとセレクティングを用いることで, 情報理論的下する多項式時間セレクティングアルゴリズムの存在を界を達成するサイズまで情報を圧縮することが可能と示し, そのアルゴリズムに対応するランキングアルゴリなる.

ズムの存在も示した.

本研究では効率的な多項式時間セレクティングアルゴリズムに焦点を当てる.

3.2

タイトセレクティング
表 1. 行列式計算により多項式時間で数え上げ可能な離散構造の一覧. グラフに対しては頂点数を n,2 背景と既存研究行列に対しては, 行数を r, 列数を n とする.

セレクティングは２つの問題を部分問題として含む.
要素の数え上げと１つの要素の出力である.
要素の数え上げは一般的には難しい問題である. セ離散構造

計算量

数え上げセレクティング
サンプリング

全域木O(nω )

Kirchhoﬀ

Colbourn,Myrvold, Neufeld

有向全域木

O(nω )

TutteColbourn,
Myrvold, NeufeldO(nω )

Kasteleyn

Mucha, Sankowski

O(nr ω−1 )WebbThis workO(nr ω−1 )Oki,MatoyaThis work

レクティングアルゴリズムに対する入力が正当か判定するためには, 集合の要素の個数を計算する必要である
ため, 数え上げはセレクティングの実行に不可欠であPf. 完全る. しかし, ほとんどの数え上げ問題は #P-困難であマッチングり, NP 困難より難しい計算量クラスに属する.

Pf. Pair

行列木定理により, グラフ上の全域木の個数はラプラシアン行列の行列式で計算することが可能である. この共通基

Pf. Parity
パリティ基

行列木定理を拡張することで, 行列式計算により多項式時間数え上げすることが可能な離散構造が数多く知られている [3].
条件を満たす要素を１つ出力する問題に対しては数多くの多項式時間アルゴリズムが開発されてきた. 中でも, 与えられたグラフ, 線形マトロイド交叉等に対して,最大マッチング, 共通独立集合等 を出力する行列を用いた代数的アルゴリズムが近年研究されている [2].
多項式時間数え上げ可能離散構造として最も単純な行列式を用いた多項式時間数え上げアルゴリズムが知られている離散構造に対して, 行列式計算一回と同じ計算量でのセレクティングアルゴリズムを新たに提示した. マトロイド交叉, マトロイドパリティ問題の行列を用いた定式化に基づいた, 分割統治法による行列式計算と同じ計算量でマトロイド交叉, マトロイドパリティ問題を解く代数的アルゴリズムに基づいたものである.
表 1 に結果を纏めた.

高速行列積による効率的セレクティングアルゴリズム (的矢 知樹)

3.3

重み付きセレクティングとが出来る. しかし, 一般のパフィアンペア, パフィア

表 2. 多項式時間で数え上げ可能な重み付き離散構造の一覧. グラフに対しては頂点数を n, 辺数をm, 行列に対しては, 行数を r, 列数を n とする.

ンパリティに対して構成されたアルゴリズムをそのまま適用すると計算量が悪化する. 表現行列の疎性を定式化する (p, q)-分割的疎という枠組みを導入し, 表現行列が (p, q)-分割的疎である場合パフィアンペア, パフィア

離散構造

計算量

数え上げ

SelctSample

最小全域木

O(nω )

Broder, MayrThis

向全域木, マッチングをパフィアンペア, パフィアンパ

最小有向全域木

O(nω )

Hayashi, IwataThis

リティとみなして適用しても現在最速のアルゴリズム

O(mn+n2 log n+nω )MatoyaThisO(nr ω +nr log n)Oki, Matoya

Thisが, 平面グラフやより一般的に K3,3 をマイナーとしてOki, Matoya

ThisO(nω+1+n3 r)

含まないグラフは, パフィアン向き付けが存在し, 多項O(n3 r)

Pf. 最小完全マッチング

Pf. pair
最小共通基

Pf. parity
最小パリティ基

ンパリティに対するアルゴリズムを提案し, 全域木, 有と同じ計算量となるアルゴリズムを提示した.
セパレータ定理による高速化

3.5

グラフのパフィアン向き付けは一般には存在しない

最小重み全域木, 最小有向全域木, パフィアングラフの最小完全マッチング, パフィアンペアの最小共通基,パフィアンパリティの最小パリティ基はそれぞれ多項式時間でパフィアン向き付けを求めることが出来る. グ
ラフのセパレータ定理を用いて, グラフ H をマイナーとして含まないグラフに対して, 完全マッチングや最小重みマッチングのセレクティングアルゴリズムを高速化した. 表 4 は結果をまとめたものである.

式時間数え上げが知られている. これらの離散構造に対

表 4. パフィアン向き付けされたグラフ上の完全マッし, 多項式時間セレクティングアルゴリズムの存在を示

チング, 最小完全マッチングのセレクティングし, 最小全域木と有向全域木に対しては行列式計算と同アルゴリズム. グラフの頂点数を n, 辺数を mとする.

じ計算量で, 完全マッチングと最小共通基に対しては,それらのインスタンスを１つ求めるために必要な計算

グラフ制約

重み量と同じ計算量でのセレクティングアルゴリズムを提–重みなし

Mucha, Sankowski

O(nω )

示した. 表 2 は結果を纏めたものである.

平面

重みなし

Mucha, SankowskiO(nω/2 )重みなしThis work (Folklore)O(nω/2 )重み付きThis workO(mn+n2 log n+nω )重み付きThis workO(n3/2log n)

これらのアルゴリズムは, それぞれの問題の双対問題の解を求め, 相補性条件を用いて最小重みインスタンスであることの同値条件を構成する手法である.

3.4

H マイナー
フリー–計算量

スパース性に基づいた高速化
H マイナー

表 3. (p, q)-分割的疎なパフィアンペア, パフィアン

フリー

パリティの具体例と, そのセレクティング計算量. 頂点数を n, 辺数を m とする.

分割的疎既存手法の計算量提案手法の計算量

グラフの全域木(1, 2)

O(nω )

O(nω )

有向グラフの有向全域木(1, 2)

O(nω )

O(nω )

パフィアングラフの完全マッチング(1, 2)

O(nω )

O(nω )(1, 3)

O(mnω−1 )O(n3 )

離散構造(p, q)-

3-パフィアン 3-正則
ハイパーグラフの全域ハイパー木

全域木, 有向全域木はパフィアンペアとして捉えることが出来, マッチングはパフィアンペアとして捉えるこ

参考文献[1] C. Colbourn, W. Myrvold, and E. Neufeld. Two algorithms for unranking arborescences. Journal of Algorithms, 20(2):268–281, 1996.
[2] N. J. A. Harvey. Algebraic algorithms for matchingand matroid problems. SIAM Journal on Computing,39(2):679–702, 2009.
[3] K. Matoya and T. Oki. Pfaﬃan pairs and parities:
Counting on linear matroid intersection and parityproblems. In Proceedings of the 22nd Conference onInteger Programming and Combinatorial Optimization, volume 12707 of LNCS, pages 223–237.