The matching problem is the most fundamental combinatorial optimization problem solved in polynomial time. In the book Matching Theory, Lovasz and Plummer say:

Matching theory serves as an archetypal example of how a "well-solvable" problem can be studied. It also seems to be very near the limits of well-solvability in a sense. Most reasonable generalizations of the matching problem have turned out to be difficult---usually NP-hard---problems.

In fact, the outstanding works for the matching problem by Edmonds in the 1960s pioneered a new field of discrete mathematics, called polyhedral combinatorics. His results have formed a basis of study on combinatorial optimization up to the present time.

The main topics of this thesis are two generalizations of the matching problem. One is the independent even factor problem, which is a common generalization of the matching and matroid intersection problems. The other is the Kt,t-free t-matching problem in bipartite graphs, which is a generalization of the matching problem and a relaxation of the Hamiltonian cycle problem in bipartite graphs.

Both of these two problems are NP-hard in the most general settings. Under certain natural assumptions, however, these two problems become tractable. Important theorems for the matching problem such as a dual integrality theorem (the Cunningham-Marsh formula) and a decomposition theorem (the Edmonds-Gallai decomposition) are extended to the even factor problem in odd-cycle-symmetric digraphs. A dual integrality theorem for the Kt,t-free t-matching problem is also established for bipartite graphs whose edge-weight is vertex-induced on any Kt,t. The two problems can be solved in polynomial time by the ellipsoid method under these assumptions.

From the viewpoint of designing combinatorial algorithms for the two problems, Pap's work was a breakthrough. For the unweighted cases, he succeeded in extending Edmonds' matching algorithm to the even factor problem in odd-cycle-symmetric digraphs and the Kt,t-free t-matching problem in bipartite graphs.

In this thesis, we extend Pap's work to weighted independent even factors and to weighted Kt,t-free t-matchings. That is, we devise combinatorial algorithms for the weighted independent even factor problem in odd-cycle-symmetric weighted digraphs and for the weighted Kt,t-free t-matching problem in bipartite graphs whose edge-weight is vertex-induced on any Kt,t. Our approach is to extend classical combinatorial algorithms such as the weighted matching algorithm, the weighted matroid intersection algorithm, and the minimum-cost flow algorithm. Our algorithms provide constructive proofs for the dual integrality and decomposition theorems. We also claim that the assumption of odd-cycle-symmetry for the even factor problem is reasonable, by showing that it is a necessary and sufficient condition for the even factors to induce a jump system.

グラフ・ネットワークに代表される離散構造の中で最適な対象を求める組合せ最適化問題の中には、問題の性質を利用して効率的に解くことのできるものと、本質的に全ての可能性を列挙せざるを得ないと考えられている問題とがある。実用上有用な組合せ最適化問題の多くが後者に属するNP困難問題であるとはいえ、近似アルゴリズム等の現実的な対処法を開発するためにも、効率的に解ける問題に対する深い知見が必要とされる。とくに、個別の問題に対する解法の効率化だけでなく、できるだけ一般的な枠組みを設定して、効率的に解ける仕組みを把握することが肝要である。このような問題意識に基づいて、組合せ最適化の研究が始められて既に半世紀が経過している。

本論文は、効率的に解くことのできる組合せ最適化問題の中でも特に精緻な構造を有するマッチング問題の一般化を論じている。マッチング問題は、線形計画法の双対理論とグラフ探索アルゴリズムの融合による効率的な解法が知られている一方で、単純な一般化ですらNP困難になってしまうという点で、多項式時間で解ける問題のクラスの境界にあると認識されている。本論文では、最近提案された一般化に対して、組合せ的な多項式時間時間アルゴリズムを設計することによって、マッチング問題に対する古典的な手法の汎用性を示すと同時に、NP困難問題との境界に関する新たな視座を提供している。

本論文は、「Combinatorial Algorithms for Generalized Matching Problems」(マッチング問題の一般化に対する組合せ的アルゴリズム)と題し、9章からなる。

第1章「Introduction」(序論)では、本論文の背景となる組合せ最適化の概要を紹介した後、本論文の主要な成果を概説している。

第2章「Preliminaries」(準備)では、マッチング問題とマトロイド交叉問題の概要を紹介した後、両者の共通の一般化として、Cunningham-Geelen(1997)の独立パスマッチング問題と Bouchet-Cunningham(1995)のジャンプシステムを詳述している。

第3章「Even factors」(偶因子)では、パスマッチングのさらなる一般化に当たる有向グラフ上の偶因子問題に関する既知の結果を整理している。有向グラフ中の偶因子のうちで最大枝数のものを見出す問題は、一般にNP困難であるが、奇閉路対称性を持つ有向グラフにおいては、Pap(2007)が提案した増加道アルゴリズムによって、多項式時間で解くことができる。

第4章「Weighted even factors」(重み付き偶因子)では、奇閉路対称性を持つ重み付き有向グラフ上で、最大重みの偶因子を見出す組合せ的な多項式時間アルゴリズムを提示している。このアルゴリズムは、Kiraly-Makai(2004)による線形計画緩和とPap(2007)の増加道アルゴリズムの手法を融合させたものであり、線形計画緩和問題における双対整数性の別証明をも与えている。

第5章「Independent even factors」(独立偶因子)では、偶因子問題とマトロイド交叉問題の共通の一般化に当たる独立偶因子問題を導入し、Papの増加道アルゴリズムを拡張することによって、組合せ的な多項式時間解法を与えている。さらに、マッチング理論におけるEdmonds-Gallai分解とマトロイド交叉問題に関連した基本分割の共通の一般化に当たる分解原理を与えている。

第6章「Weighted independent even factors」(重み付き独立偶因子)では、第4章と第5章の結果を拡張して、最大重み独立偶因子を見出すアルゴリズムを与えている。

第7章「Jump systems and discrete concave functions arising from even factors」(偶因子の定めるジャンプシステムと離散凹関数)では、有向グラフ中の偶因子の次数列全体の組合せ論的性質を調べている。とくに、次数列全体がジャンプシステムをなすための必要十分条件が、有向グラフの奇閉路対称性であることを示している。さらに、偶因子の重みから誘導される関数がジャンプシステム上のM凹関数になるための必要十分条件が、重み付き有向グラフの奇閉路対称性であることも証明している。これらの結果は、独立に展開されてきた偶因子の研究とジャンプシステムの研究とを結び付けるだけでなく、組合せ最適化問題の多項式時間可解性を離散構造の言葉で特徴付けている点で非常に興味深い。

第8章「Weighted Kt,t-free t-matching」(重み付きKt,t -free tマッチング)では、2部グラフ中で完全2部グラフKt,tを含まないtマッチングのうちで最大重みのものを求める問題を扱っている。この問題も一般にはNP困難であるが、部分グラフKt,t上での重みが頂点重みから誘導されるという条件の下で、組合せ的な多項式時間アルゴリズムを示している。枝数の最大化問題に対してHartvigsen(2006)とPap(2007)によって、組合せ的なアルゴリズムが提案されていたが、両者とは異なるアルゴリズムを新たに設計することによって、重み付きの場合への拡張を可能にしている。このアルゴリズムは、線形計画緩和問題の双対整数性に関するMakai(2007)の定理に対する別証明をも与えている。

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

以上を要するに、本論文は、多面体的組合せ論、グラフアルゴリズム、離散凸解析の最近の進展を踏まえた上で、組合せ最適化手法に関する知見を深化させるものであり、数理情報学の発展に大きく貢献するものである。

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