研究紹介

概要

グラフ理論・離散最適化・アルゴリズムの研究をしています．

グラフの構造に興味がありますが，最適化理論や離散アルゴリズムにもモチベーションをおいています．

とくに，マッチング理論（因子理論）におけるグラフの標準分解の理論に取り組んできました．

これまでの成果には，新しい標準分解理論の提案，およびその理論的応用があります．

他，マイナーインタレストとして，二分決定ダイヤグラム（Binary Decision Diagram; BDD）や組合せ的行列理論（Combinatorial Matrix Theory) があります．

マッチング理論（matching theory）とは

グラフのマッチング（1-マッチング）とは点を共有しない枝の集合のことをいいます．

つまりこれはペアリングの最も基本的な表現方法になります．

マッチングは置換のような偶奇性と関わりが深い諸概念と結びつくことも知られており，行列式やパーマネントとも関連します．

マッチング（1-マッチング）には b-マッチングや T-ジョインをはじめとする膨大な種類の亜種・一般化が知られており，

これらに関する研究成果はマッチング理論と呼ばれるグラフ理論・離散最適化における一大分野を成しています [Lovasz'86]．

また，最大マッチング問題（与えられたグラフにおける最大濃度のマッチングを求める問題）は多項式時間可解性を象徴する最適化問題として位置づけられています [Lovasz'86, Schrijver'03]．

多面体的組合せ論（polyhedral combinatorics) のパラダイムは最大マッチング問題の研究をきっかけとして展開されました．

また，最大流問題およびマトロイド交差問題は共に劣モジュラ関数（submodular function）の理論における代表的な問題ですが，2部グラフの最大マッチング問題は最大流問題のサブクラスであると同時にマトロイド交差問題の原型となっています．

グラフの標準分解とは

マッチング理論の研究においては，総称して標準分解（canonical decomposition）と呼ばれるグラフの分解（分解型構造定理）が役に立ちます．

標準分解はいずれも，与えられたグラフに対して一意に定まる分解を与え，それに沿ってグラフが持つ全てのマッチングの構造を一括して記述します．故に標準分解は非常に強力で汎用性が強く，マッチング研究の理論基盤となってきました．

マッチング理論における標準分解の役割とは，ちょうど線形代数における各種の標準形の役割に似ています．

行列に関する問題が与えられたとき，その問題に応じた種類の標準形を選び行列を分解することによって強力なオブザベーションが得られます．

それと同様に，グラフに関する問題が与えられたとき，適切な標準分解で以ってグラフに構造を入れることによって問題を解く上でのキーオブザベーションが得られます．

新しい標準分解理論：一般カテドラル分解

任意のグラフに用いられる新しい標準分解として一般カテドラル分解（general cathedral decomposition）を提案しました [1-3]．文献によってはバシリカ分解（basilica decomposition) と呼んでいます．

位置づけ

古典的には標準分解として，Gallai-Edmonds 分解（Gallai '64, Edmonds '65），Kotzig-Lovasz 分解（Kotzig '59-60, Lovasz '72），Dulmage-Mendelsohn 分解（'58-'63）の３つが知られていました．しかし，それぞれ対象とするグラフが特殊なクラスに限られている，あるいは分解の目が粗いなどの問題点があり，また，これら相互の論理的な関連も不明でした．

これに対し，新しい標準分解として，一般カテドラル分解を提案しました．一般カテドラル分解は，任意のグラフを適用対象とし，かつ既存の標準分解の一般化，あるいは細分を含んでいます．これにより，これまでばらばらに理解されていた古典的な標準分解たちを統一的に理解することも可能になりました．

より具体的には，Gallai-Edmonds 分解に対してはその細分を，Kotzig-Lovasz 分解に対してはその一般化を与え，さらに変形解釈することで Dulmage-Mendelsohn 分解の一般化を導出します [4]．

理論の詳細

一般カテドラル分解の理論は因子成分（factor-component）の概念に基く３つの主定理から成ります．

因子成分とはマッチングを考察する上でグラフの構成単位とみなせる部分グラフです．任意のグラフは因子成分いくつかを枝でつないでできた格好をしています．

主定理１：カテドラル順序の存在

因子成分の集合がどのように枝で接続されグラフ全体を構成しているかには規則性があります．

その規則は因子成分の集合上にある2項関係を定義しそれが半順序であることを示すことによって特徴付けられます．

これを因子成分のカテドラル順序と呼びます．

主定理２：一般化 Kotzig-Lovasz 分解

これは因子連結グラフ（factor-connected graph）に対する古典的な Kotzig-Lovasz 分解の一般化であり，

因子連結とは限らない一般のグラフにおいては，因子連結グラフの内部構造を記述するものになります．

古典的に Kotzig が与えた定理と同様，グラフの点集合の上にある2項関係を定義し，これが同値関係であることを示すことによって，因子成分の内部構造がこの同値関係の商集合として明らかになります．この構造が一般化 Kotzig-Lovasz 分解です．

主定理３：カテドラル順序と一般化 Kotzig-Lovasz 分解の相互関係

カテドラル順序および一般化 Kotzig-Lovasz 分解は独立に定義され証明されるにも関わらず，ある相互関係があります．

この２つの相互関係により，グラフを物理的な建築物のように理解する構造が浮かび上がります．

これをグラフの一般カテドラル分解と呼びます．

一般カテドラル分解の理論的応用

Lovasz の飽和カテドラル定理の別証明 [5, 6]

グラフが「飽和している」とは，いかなる補枝の添加に対しても新たなマッチングが生じないことをいいます．Lovasz の飽和カテドラル定理（the cathedral theorem for saturated graphs, 1972）は飽和グラフの帰納的特徴づけとなる定理であり，マッチングの数え上げに利用されることが知られています．飽和カテドラル定理は Lovasz らによる書籍 [Lovasz'86] でも節を割いて紹介されています．新しい標準分解を用いることで飽和カテドラル定理の別証明が得られます．

タイトカット補題のグラフ理論的別証明 [9, 10]

タイトカット補題（the tight cut lemma; Edmonds, Lovasz & Pulleybalnk, 1982）は Edmonds らによる完全マッチング多面体の研究において提案されました．Edmonds らの結果は完全マッチング多面体の次元が，ひとつのグラフを構成するブリック（brick，3連結双臨界グラフ）の集合よって特徴づけられるということを明らかにしたものです．タイトカット補題は，Edmonds らによるこの結果の導出における key lemma となります．タイトカット補題は Lovasz らや Schrijver の書籍 [Lovasz'86][Schrijver'03] でも節を割いて紹介されています．

タイトカット補題の主張そのものはグラフ理論的ですが Edmonds らによる証明は線形計画法の議論を用いたものでした．

新しい標準分解を用いることでタイトカット補題のグラフ理論的な証明が得られます．

マッチングの双対最適解の標準的特徴づけ [7, 8]

双対性はいわずもがな最適化理論の根幹をなす概念です．

最大マッチング問題に関する双対定理，すなわち Berge 公式（Tutte-Berge 定理）は古くから知られており，その双対最適解も古典的に重要さが認識されマッチング研究の道具として用いられて来ました．ですがそれにもかかわらず，マッチングの双対最適解そのものについて知られていることは非常に少ないという状態が続いていました．

対して，新しい標準分解を用いることで，マッチングの双対最適解に構造的特徴づけを与えることができます．ここではグラフにおけるどのような点集合が双対最適解を成すのかが新しい標準分解の言葉で特徴づけられます．この中で一般のグラフにおいてマッチングの双対最適解の族が成す束論的構造，すなわちマッチングの双対最適解となる点集合はグラフによって定まるあるポセットのイデアルであることが明らかになっています．

一般カテドラル分解のさらなる発展

T-ジョインの標準構造

グラフと点の集合Tが与えられとき，T-ジョインの概念が定義されます．T-ジョインはパリティ性の観点から与えられた，完全マッチングの概念の一般化に相当します．また T-ジョインはその特殊ケースとして最短路問題や中国人配達夫問題など無向グラフ上の経路問題をいくつか含む他，整数フローに関する未解決予想と関連が深いことが知られています．一般カテドラル分解の理論を発展させることで T-ジョインの標準構造を記述する分解定理が得られます．

引用文献

[Lovasz'86] L. Lovász and M. D. Plummer: Matching Theory. North-Holland Publishing Co, 1986.

[Schrijver'03] A. Schrijver: Combinatorial Optimization. Polyhedra and Efficiency. Springer-Verlag, 2003.