One of the central topics in graph theory is a characterization of graphs containing a certain structure such as a path, a cycle, a tree, a matching with some conditions. Since 1950s, the importance of finding such structures has been recognized also by computer scientists, because graphs appear in many practical situations. For example, graphs are abstractions of transportation networks, VLSI, social networks, protein interaction networks, web graphs, and so on. Today, there are many studies on efficient algorithms for finding such structures in graphs.

The central topic of this thesis is finding "disjoint paths" in a given graph efficiently. More precisely, when we are given a graph and pairs of vertices in the graph, we would like to decide whether or not the graph has paths such that they are mutually disjoint and each path connects given pairs of terminals. This problem has attracted attention in the contexts of transportation networks, VLSI-layout and virtual circuit routing in high-speed networks or Internet. A basic technical problem is to interconnect certain prescribed "channels" on the chip with wires, where wires belonging to different pins do not touch each other. In this simplest form, the problem amounts mathematically to finding disjoint trees or disjoint paths in a graph, each connecting a given set of vertices. The concept of disjoint paths, which is closely related to connectivity of a graph, is important also in graph theory.

The problem of finding disjoint paths has many variants depending on whether the input graph is directed or undirected, whether "disjoint" means vertex-disjoint or edge-disjoint, whether the input graph is planar or not, and so on. The main aim of this thesis is to study computational complexities of these variants. In particular, we aim to give efficient algorithms for these variants. It is theoretically interesting that the computational complexities of these variants are completely different from one another, whereas the variants have similar forms. Besides the theoretical interest, efficient algorithms for the problems are useful in practice when they arise from practical situations.

In the field of theoretical computer science, an algorithm is considered to be "efficient," if its running time is proportional to a small-order polynomial of the input size such as the number of vertices of a graph. However, it is known that there exists a class of hard computational problems, which are called NP-hard problems. The concept of NP-hardness was developed in the early 1970s, and it is believed by most researchers today that there is no polynomial-time algorithm for NP-hard problems. With this background, for a problem of finding disjoint paths, our objectives are the following:

(1) Giving a polynomial-time algorithm for the problem or else showing the NP-hardness.

(2) Giving an efficient algorithm for the problem if it is polynomially solvable, i.e.,giving an algorithm whose running time is a small-order polynomial of the input size.

グラフは、交通網や集積回路等の数学的抽象化として、様々な場面に現れる概念である。現実問題の中には、与えられたグラフの中に、木、パス、マッチング、サイクルといった特定の部分構造を見出す形にモデル化できるものが数多く存在する。大規模なグラフにおいてこの種の部分構造を見出すための、効率的なアルゴリズムの構築は、情報科学および離散数学の分野における重要な課題と認識され、計算機科学の成立以来、半世紀にわたり、実用・理論の両面から活発な研究が続けられている。歴史を振り返ってみると、効率的な解法の構築に関する研究の画期には、その背景としてグラフの数学的性質に関する理論の進展が見られる。

本論文は、近年整備されたグラフマイナー理論を軸に据え、その成果を直接的あるいは間接的に利用することによって、指定頂点対を結ぶ互いに素なパスを見出す問題およびその変種に対して、効率的解法を設計して提案するものである。特に、点素パス問題およびあるクラスのグラフ上の辺素パス問題に対しては、既存解法よりも高速な解法を設計している。さらに、その問題と密接な関係にある最短点素パス問題と誘導点素パス問題に対しても、効率的な解法を与えている。

本論文は「Algorithms for Finding Disjoint Paths: Acceleration and Extension」(点素パス問題に対する算法:高速化と拡張)と題し、10章からなる。

第1章「Introduction」(序論)では、点素パスに関連する様々な問題の概要を記述した後、本論文の主要な成果を概説している。

第2章「Preliminaries」(準備)では、数学的な議論の準備として、グラフに関する記法や基本的性質が述べられている。

第3章「Notable Special Cases」(重要な特殊ケース)では、特筆すべき先行研究が纏められている。素なパスに関する先行研究が、古典的な最大 s-t パス問題から近年の結果に至るまで幅広く扱われている。

第4章「Graph Minor Theory」(グラフマイナー理論)は、グラフ理論における最先端の研究成果であるグラフマイナー理論をアルゴリズム的な側面を中心として記述している。グラフマイナー理論は、1980年代から Robertsonと Seymour によって構築された離散数学における一大理論体系であり、無向グラフ上の点素パス問題に対する多項式時間解法を始めとして、多くの効率的アルゴリズムの設計に応用されている。

第5章「Quadratic-Time Algorithm for the Disjoint Paths Problem」(点素パス問題に対する2乗時間アルゴリズム)では、無向グラフ上の点素パス問題に対して、計算時間が頂点数の2乗に比例するアルゴリズムを提案している。この問題に対しては、Robertson-Seymour (1995) によってグラフマイナー理論に基づく多項式時間解法が与えられていたが、それは極めて難解で複雑であった。本章の解法は、Robertson-Seymourのアルゴリズムの構造をより精査することによって、計算時間を頂点数の3乗のオーダーから2乗のオーダーに高速化している。

第6章「Edge-Disjoint Paths Problem in Eulerian Graphs」(オイラーグラフ上の辺素パス問題)では、ある制約を満たすグラフ上の辺素パス問題に対して、単純で効率的な解法を提案している。辺素パス問題に対しては Robertson-Seymour (1995) の多項式時間解法があるが、この解法には、正当性証明の難解さと計算時間の膨大さという2つの問題点があった。本章では、グラフがオイラー性や4辺連結性をもつ特殊ケースに対して、単純で効率的な解法を与えている。

第7章「Shortest Disjoint Paths Problem」(最短点素パス問題)では、目的関数最小の点素パスを見出す問題を導入している。現実的な問題のモデル化を考えると、点素パスの中で費用の小さいものを見出すことが自然に要請される。本章では、グラフの種類、頂点対の数、目的関数などを変化させた場合に対して、効率的解法の提案や計算複雑度の解析を行っている。

第8章「Induced Disjoint Paths Problem」(誘導点素パス問題)では、誘導点素パス問題を導入し、様々な形式の問題を解析している。誘導点素パス問題とは、指定頂点対を結ぶ点素パスで互いに隣り合わないものを見出す問題であり、点素パス問題の自然な拡張である。本章では、様々な形式の誘導点素パス問題に対して、効率的解法の提案や計算複雑度の解析を行い、点素パス問題との類似や差異を解明している。とくに、平面有向グラフ上の問題に対する多項式時間解法と、平面無向グラフ上の問題に対する線形時間解法が主要な結果である。

第9章「Induced Cycle Problem」(誘導サイクル問題)では、指定頂点を通る誘導サイクルを見出す問題に対して効率的解法を提案している。この問題は、誘導点素パス問題に関連して自然に生じる問題であり、また、誘導サイクルは、パーフェクトグラフとの深い関連が最近明らかにされたことで、グラフ理論における重要な構造として認識されるに至っている。本章では、平面グラフ上の誘導サイクル問題に対して,線形時間解法を与えている。

最後に第10章「Conclusion」(結論)では、本論文の成果を簡潔に纏めると共に、今後の研究課題を提示している。

以上を要するに、本論文は、離散数学の最先端の結果を駆使して、点素パスに関連した様々な問題に対する効率的なアルゴリズムを構築したものであり、数理情報学の発展に大きく貢献するものである。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。