Computing shortest paths in graphs is one of the most fundamental and well-studied problems in combinatorial optimization. Numerous real-world applications have stimulated research investigations for more than 50 years. Finding routes in road and public transportation networks is a classical application motivating the study of the shortest path problem. Shortest paths are also sought by routing schemes for computer networks: the transmission time of messages is less when they are sent through a short sequence of routers. The problem is also relevant for social networks: one may more likely obtain a favor from a stranger by establishing contact through personal connections.

This thesis investigates the problem of efficiently computing exact and approximate shortest paths in graphs, with the main focus being on shortest path query processing. Strategies for computing answers to shortest path queries may involve the use of pre-computed data structures (often called distance oracles) in order to improve the query time. Designing a shortest path query processing method raises questions such as: How can these data structures be computed efficiently? What amount of storage is necessary? How much improvement of the query time is possible? How good is the approximation quality of the query result? What are the tradeoffs between pre-computation time, storage, query time, and approximation quality?

For distance oracles applicable to general graphs, the quantitative tradeoff between the storage requirement and the approximation quality is known up to constant factors. For distance oracles that take advantage of the properties of certain classes of graphs, however, the tradeoff is less well understood: for some classes of sparse graphs such as planar graphs, there are data structures that enable query algorithms to efficiently compute distance estimates of much higher precision than what the tradeoff for general graphs would predict. The first main contribution of this thesis is a proof that such data structures cannot exist for all sparse graphs. We prove a space lower bound implying that distance oracles with good precision and very low query costs require large amounts of space. A second contribution consists of space- and time-efficient data structures for a large family of complex networks. We prove that exploiting well-connected nodes yields efficient distance oracles for scale-free graphs. A third contribution is a practical method to compute approximate shortest paths. By means of random sampling and graph Voronoi duals, our method successfully accommodates both highly structured graphs stemming from transportation networks and less structured graphs stemming from complex networks such as social networks.

最短路問題は、コンピュータ科学における基本的問題であるとともに、道路網、輸送ネットワーク、コンピュータネットワークなど多様な応用が可能な問題で、その研究の歴史も長く、多くの研究成果がこれまでにあげられている。しかしながら、事前にネットワークを処理して適切なデータ構造を構築することにより、指定された2点がクエリとして与えられたとき、高速にその最短路長あるいはその近似を答えるという最短路検索という新世代の問題については、理論的にも実際的にも未解決な問題が多数ある状況であった。本論文では、この最短路検索に対して、従来の理論的計算量下限に関する未解決問題を解くとともに、実際的なアルゴリズム提案とその理論解析を与えることにより、この新世代の最短路問題の研究における大きな展開を実現したものである。

最短路検索問題では、理論的な観点および応用面での種々の要求から、次のような課題がある:(a) 事前に構築するデータ構造の構築にかかる計算時間、(b) 構築されたデータ構造のサイズ、(c) クエリに対してこのデータ構造により実現される検索時間、の3つの複雑度に加え、(d) 最短路長の近似値を答えることを許容した場合の許容する近似精度、という新しいパラメタを加えた4つの複雑度に関するトレードオフとそれぞれの複雑度の限界の解明すること。本論文では主に(b), (c), (d)の3パラメタに関するトレードオフに着目して問題解決に取り組んでいる。

まず、一般のグラフに対するデータ構造のサイズ、検索時間そして近似精度に関するトレードオフがある点について、検索時間を含む下限を初めて与え、それを疎なグラフに対しても有効に適用できることを示した。具体的には、n 点のグラフが与えられたとき、検索時間 t と最短路長の高々α倍まで許容するという近似精度に関する要件のもと、データ構造のサイズの下限をn, t, αの具体的関数によって与えている。この下限は検索時間 t を含む初めてのものである。下限を達成する具体的グラフクラスも示されている。この結果をさらに展開することにより、疎なグラフに対して枝数サイズのデータ構造で定数検索時間を達成するといった理想的解決は不可能であることを示している。これらの結果は通信計算量解析の手法を用いて行われており、手法の観点からも興味深いものとなっている。この成果はIEEE 50th Annual Symposium on Foundations of Computer Science (FOCS) というハイレベルの国際会議で採択され、国際的に高く評価されている。

次に、グラフのクラスで次数列がべき乗則を満たすものに対して、サイズと検索時間の両面で有効なデータ構造を与え、理論的解析を行っている。べき乗則を満たすグラフは、Webリンクグラフなど現実世界のスケーラブルなネットワークの多数がこの条件を満たすものとして知られている。一般のグラフに対する既存研究結果を適用しても、定数近似精度での最悪の場合は実際にはこのクラスのグラフでは観察されておらず、一般のグラフに対する結果を越えるような、この有用なグラフに対して有効な方法の提案およびその理論的解析がなされていなかった。べき乗則を満たすグラフでは、次数が低い点が多く、次数が高い点が少ないグラフである。このクラスのグラフでは、最短路は往々にして高い次数の点を通ることに着目し、このような性質を活用して、非常に実用的な近似解法が開発されている。近似解法の理論的解析を、べき乗則を満たすランダムグラフのクラスに対して行うことにより、この近似解法の理論的解析と実際的効率の間の関係をべき乗則の次数を用いて確率的に解明することに成功している。

また、本論文は一般のグラフに対してランダムサンプリングとグラフVoronoi図を活用することによって、最短路長検索の問題に対して理論的近似精度保証を有する効率的アルゴリズムを与えている。前処理においては、グラフVoronoi図の双対を活用し、検索においてはその双対グラフ上での探索結果を元のグラフの上でそれをさらに精緻化することを行っている。理論的に近似値比の期待値が高々最短路長の点数の対数でおさえられることが証明されている。その上で、既存研究の代表的な実用的アルゴリズムとの計算機実験による比較を行い、提案手法の有効性が定量的に示されている。

以上をまとめるに、本論文では最短路検索問題に関して、理論的に検索時間を含めたトレードオフの限界を示し、疎なグラフの場合にも有効な理論的成果を確立するとともに、現実的なネットワークのべき乗則を満たすグラフのクラスでの実用的アルゴリズムの提案とその確率的な理論解析、そして平面構造等の現実的性質を有するグラフでの高速アルゴリズムを提案するという成果をあげており、この基本的問題である最短路検索について、理論と応用の観点から新たな展開をもたらしている。よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。

なお本論文の成果は共同研究によって得られたものであるが、申請者が主体的に研究を行って得られたものであることを確認している。