修士論文 要旨

動的区間最頻値問題と頂点発見問題の効率的アルゴリズム
数理情報学専攻 48206208
指導教員

小畑 哲雅
定兼 邦彦 教授

列 を L = Θ(N α ) 個 の 長 さ C

1 動的区間最頻値問題()= Θ N 1−α(0 ≤ α ≤ 1)．以下の部分列に分割し、適切に挿入や定義 1 (mode). A : multiset

削除、及び各部分列間での要素の受け渡しを行うことにa ∈ A が A の mode ⇔ ∀b ∈ A (a の A での重複度)

よって、各クエリを高速に処理することが出来る。

≥ (b の A での重複度)

insert, delete によって列のサイズが大きく変化したmode を扱う問題として、 Range mode problem が存在する。

場合、 L の値を変更する必要がある。これに対処する為に、動的データ構造のテクニック [7] を用いる．デー
タ構造を一定数のクエリ毎に再構築することで、各クエ問題 2 (Range mode problem). アルファベット集合

リの時間計算量を償却計算量で評価することが出来る。

Σ 上の列 A が与えられたとき，以下のクエリから成る

更に、次の再構築後に使用するデータ構造を各クエリのクエリの列を処理せよ．

タイミングで少しずつ準備することによって、各クエリ• mode(l, r): A[l : r] の mode を 1 つ出力する．
Range mode problem は Set intersection problem
等への応用が知られており [1]， 多くの先行研究が存在する [1] [2] [3] [4] [5] [6]．

Range mode problem を拡張した問題として， Dynamic range mode enumeration problem が 考 え られる．の時間計算量を最悪計算量で評価することが出来る。

2 頂点発見問題
以下の形式で表される問題を考える．
問題 5. 辺の情報が未知であるグラフが存在する．以下のクエリを何度でも行うことが出来る．

• probe (u, v): 頂点 u と頂点 v の間の辺についての問題 3 (Dynamic range mode enumeration problem).

情報を得ることが出来る．

アルファベット集合 Σ 上の列 A が与えられたとき，以可能な限り少ない回数のクエリを用いて，グラフについ下のクエリから成るクエリの列を処理せよ．ての「ある性質」を調べよ．

• insert(c, i): c (∈ Σ) を A の i 番目に挿入する．

この問題は，グラフの性質を効率良く特定しようとす• delete(i): A の第 i 要素を削除する．

るアルゴリズムと，グラフの性質を特定されないように• modes(l, r): A[l : r] の mode を全て出力する．

グラフの辺の張り方を決定する戦略の対立構造と見る

dynamic range mode enumeration problem の先行研究は存在しない．

ことが出来る．probe クエリを行うことは、現実のグラフ構造を持つ対象において各ノードの関係性を調べる行為に対応しており、少ない probe でグラフの性質を定理 4 が本稿の主定理である．

調べることは、対象の全体像を効率良く調べることに役

定 理 4. dynamic range mode enumeration prob-立つ。クエリ回数の上界や下界について， 多くの研究

lem を Ω(log N + log σ) bits wordsize の word RAMが行われている． [8] [9] 特に、クエリ回数の下界がモ デ ル 上 で ， insert ク エ リ と delete ク エ リ を回となる性質は elusive であると定義され、 elusiveness(23′)

O N log σ time per query で処理し， modes ク)( 2エリを O N 3 log σ ′ + |output| time per query で処理するデータ構造が存在する．ここで，N はクエリ時点での列の長さを， σ は |Σ| を， σ ′ は列に現れる要素(の種類数を現す．空間計算量は，O N + N 3 σ ′2)

words( n)2については盛んに研究されている。 [8] [10] [11]本稿では， 以下の問題を考える。
問題 6. 各頂点組間の辺の有無及びその向き付けについての情報が未知である有向グラフが存在する．以下のクエリを何度でも行うことが出来る．

である．

• probe (u, v): 頂点 u と頂点 v の間の辺の有無及び動的区間最頻値問題と頂点発見問題の効率的アルゴリズム (小畑 哲雅)

その向き付けについての情報を得ることが出来る．
可能な限り少ない回数のクエリを用いて，出次数が丁度k である頂点を 1 つ発見せよ．或いは，そのような頂点が存在しないことを報告せよ．

0 ≤ k ≤ (n + 1) /2 の場合は， 全ての頂点組について probe する必要があることが知られている [8]．一方， (n + 1) /2 < k の場合は，probe 回数についての既知の最良の下界は，( n)2( )− k2 回である． [8]

本稿は，(n + 1) /2 < k の場合の下界を改善した．主要な定理を定理 7 に示す．
定理 7. (n + 1) /2 < k のとき，出次数 k の頂点を発( )()見するには， n2 − 2k−n+1回のクエリが必要である．
2定理 7 の評価は， 元の評価の証明 [8] における辺配置を更に密にすることで達成される．

参考文献[1] Timothy M. Chan, Stephane Durocher, Matthew
Skala, and Bryan T. Wilkinson. Linear-space datastructures for range minority query in arrays. In Fedor V. Fomin and Petteri Kaski, editors, Algorithm
Theory – SWAT 2012, pages 295–306, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
[2] Holger Petersen. Improved bounds for range modeand range median queries. In Proceedings of the 34th
Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM’08, pages 418–423. Springer-Verlag, 2008.
[3] Holger Petersen and Szymon Grabowski. Range
mode and range median queries in constant time andsub-quadratic space. Inf. Process. Lett., 109:225–228,01 2009.
[4] Mark Greve, Allan Grønlund Jørgensen, Kasper Dalgaard Larsen, and Jakob Truelsen. Cell probe lower
bounds and approximations for range mode. InSamson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G.
Spirakis, editors, Automata, Languages and Programming, pages 605–616, Berlin, Heidelberg, 2010.
Springer Berlin Heidelberg.
[5] Timothy M. Chan, Stephane Durocher, Kasper
Green Larsen, Jason Morrison, and Bryan T. Wilkinson. Linear-space data structures for range modequery in arrays. Theory of Computing Systems,55(4):719–741, November 2014.
[6] Kentaro Sumigawa, Sankardeep Chakraborty, Kunihiko Sadakane, and Srinivasa Rao Satti. Enumerating Range Modes. In Yixin Cao, Siu-WingCheng, and Minming Li, editors, 31st International
Symposium on Algorithms and Computation (ISAAC2020), volume 181 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:16,Dagstuhl, Germany, 2020. Schloss Dagstuhl–LeibnizZentrum für Informatik.

[7] Veil Mäkinen and Gonzalo Navarro.
Dynamicentropy-compressed sequences and full-text indexes.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artiﬁcial Intelligence andLecture Notes in Bioinformatics), 4009 LNCS:306–317, 2006.
[8] Dishant Goyal, Varunkumar Jayapaul, andVenkatesh Raman.
Elusiveness of ﬁnding degrees. In Daya Gaur and N.S. Narayanaswamy,
editors, Algorithms and Discrete Applied Mathematics, pages 242–253, Cham, 2017. Springer
International Publishing.
[9] Arindam Biswas, Varunkumar Jayapaul, VenkateshRaman, and Srinivasa Rao Satti. The complexityof ﬁnding (approximate sized) distance-d dominating set in tournaments. In Mingyu Xiao and Frances
Rosamond, editors, Frontiers in Algorithmics, pages
22–33, Cham, 2017. Springer International Publishing.
[10] Arnold L. Rosenberg. On the time required to recognize properties of graphs: A problem. SIGACT
News, 5(4):15–16, oct 1973.
[11] H.W. Lenstra, M.R. Best, and Peter van Emde Boas.
A sharpened version of the aanderaa-rosenberg conjecture. Report 30/74, Mathematisch Centrum Amsterdam (1974), 01 1974.