研究紹介（工事中）

概要

離散数学や理論計算機科学の研究をしています．特にグラフ理論・離散最適化・アルゴリズムなどを研究しています．

最適化理論やアルゴリズム設計にモチベーションをおき，グラフの構造を追求するテーマに主に取り組んでいます．


マッチング理論のための標準分解理論

マッチング理論とは

マッチングは基本的かつ古典的な組合せ論的概念の一つであり，マッチング理論はグラフ理論や離散最適化の代表的な分野である．グラフのマッチング（matching; 1-マッチング）とは点を共有しない枝の集合のことをいい，すなわちこれは（ネットワーク上の）ペアリングを表現する最も素朴な概念である．マッチングそのものに加え，マッチングの一般化や亜種に当たる概念も膨大な数のものが提案されており，これらに関する研究成果の蓄積あるいは体系はマッチング理論と呼ばれる．また，マッチングは置換のような偶奇性と関わりが深い諸概念と結びつくことも知られており，行列式やパーマネントとも関連するなど，組合せ行列理論（combinatorial matrix theory）における貢献などにおいても知られる．

マッチング理論における標準分解理論　　

マッチング理論おいては，総称して標準分解（canonical decomposition）と呼ばれる一連のグラフの分解定理（分解型構造定理）が理論基盤を為している．標準分解は 1960 年代頃に知られるようになり，Gallai-Edmonds 分解（Gallai '64, Edmonds '65），Kotzig-Lovasz 分解（Kotzig '59-60, Lovasz '72），Dulmage-Mendelsohn 分解（'58-'63）の３つが知られていた．これらの分解には，グラフに対して一意に定まること，さらにその分解で以ってグラフが持つ全ての最大マッチングに共通する構造を記述することなどいくつか共通する特徴があり，その類似性ゆえに標準分解の概念が自然と形成され，これら３つの分解は標準分解という枠組みの構成要素として理解されることとなった．

しかし古典的標準分解はそれぞれ特殊なグラフクラスを対象とする，あるいは分解の目が粗いことなどの問題点があった．Dulmage-Mendelsohn 分解はそれぞれ２部グラフと因子連結グラフ（factor-connected graph）を適用対象とする分解定理である．一方 Gallai-Edmonds 分解は定義上は任意のグラフを対象とするものの，与えられたグラフを二つの部分に分割し一方の内部構造を記述する定理であるため，十分な情報が引き出せないことがある，ひいては適用したい対象が既約クラスにしばしば陥るなどの問題があった．また，３つの古典的標準分解には共通する特徴があるものの，互いの論理関係は不明であり，３つの背後にありこれらを包括する枠組みは未知であった．

これに対して本研究は，一般のグラフを対象とし既存の標準分解たちを内包する新たな標準分解を導出した．まず K'12+ では，一般のグラフを対象とし，Gallai-Edmonds 分解の細分と Kotzig-Lovasz 分解の一般化を含む標準分解として一般カテドラル分解が導出された．さらに一般カテドラル分解を変形することによって Dulmage-Mendelsohn 分解を一般のグラフを対象とするものへと一般化した標準分解である非二部的 Dulmage-Mendelsohn 分解が得られた．この互いに関連する二つの標準分解が，一般のグラフを対象とし，かつ既存の標準分解が細分化あるいは一般化として含む枠組みを提供している．


標準分解の理論的応用

極大バリアの束論的特徴づけ

双対性は最適化理論の中核をなす概念である．最大マッチング問題には Berge 式と呼ばれる双対定理が知られており，Berge 式によって定義される最大マッチング問題の双対解はグラフのバリアと呼ばれる．バリアについて一般的に明らかに知られていることは非常に少なく，極大バリアについては古典的標準分解それぞれによって記述される構造的知見が知られていた．K'13 では一般のグラフにおける極大バリアの構造が一般カテドラル分解を用いて明らかにされてた．この成果によってさらに K'18 では，一般のグラフにおける極大バリアの族が非二部的 Dulmage-Mendelsohn 分解が与える半順序集合のイデアルの族として特徴づけられた．この成果は極大バリアの特徴づけとして初めてのフルリザルトであり，古典的標準分解たちによって知られていた極大バリアの構造的知見を含んでいる．

飽和カテドラル定理（Lovasz 1972）の短証明　

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

タイトカット補題のグラフ理論的別証明

タイトカット補題（the tight cut lemma; Edmonds, Lovasz & Pulleybalnk, 1982）は ，完全マッチング多面体の次元が，グラフを構成するブリックの集合によって特徴づけられることを明らかにした定理である．すなわちタイトカット補題は，その後の完全マッチング多面体の研究の方向性を決定づけた重要な定理であり，Lovasz らや Schrijver の書籍 でも節あるいは章を割いて紹介されている．Edmonds らによるタイトカット補題の証明は線形計画法の議論によるものであったが，新しい標準分解を用いることでタイトカット補題に純粋にグラフ理論的な証明が与えられる．


関連する論文

  1. N. Kita, A partially ordered structure and a generalization of the canonical partition for general graphs with perfect matchings, Lecture Notes in Computer Science, vol. 7676 , 2012, pp. 85–94.

  2. N. Kita, Disclosing barriers: a generalization of the canonical partition based on Lovasz’s formulation. Lecture Notes in Computer Science, Vol. 8286, 2013, pp. 402—413.

  3. N. Kita, An alternative proof of Lovasz’s cathedral theorem. Journal of the Operations Research Society of Japan, Vol. 57, Num. 1, 2014, pp. 15--34.

  4. N. Kita: New canonical decomposition in matching theory. arXiv: 1708.01051, 2017.

  5. N. Kita, Structure of towers and a new proof of the Tight Cut Lemma. Lecture Notes in Computer Science, Vol. 10627, 2017, pp. 225-239.

  6. N. Kita, Nonbipartite Dulmage-Mendelsohn decomposition for Berge duality. Lecture Notes in Computer Science, Vol. 10976, 2018, pp. 293-304.

参考文献

  • [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.

T-ジョイン（パリティ因子）のための標準分解理論　

T-ジョイン（パリティ因子）とは

グラフの T-ジョイン（T-join）は，無向最短経路問題を含め様々な経路問題を従える，離散最適化分野の古典的なトピックである．グラフの点の集合 T に関して，枝の集合 J が T-ジョインであるとは，各点についてそれが T の点であることと奇数本の F の枝に接続していることが同値であることをいう．パラメタ T に応じて T-ジョイン問題は，無向最短経路問題や配達夫問題（postman problem）など，様々な最適化問題を与える．また，1-因子（完全マッチング）を持つグラフにおいて， T として点集合そのものを与えると，最小 T-ジョイン と 1-因子は一致するため，T-ジョインは 1-因子の一般化としての側面も持つ．グラフの T-ジョインにはいくつかの異なる呼び名が知られており，グラフとパラメタ T のペアであるグラフト（graft）のジョイン（join）とも呼ばれる．

T-ジョインと標準分解理論

T-ジョインは 1-因子の一般化としての側面を持つがその性質は 1-因子あるいはマッチングよりもはるかに複雑であり，T-ジョインの理論的基礎はマッチングのそれと比べて未熟である．これを踏まえ，本研究は，T-ジョインのための標準分解理論を導入することによって T-ジョイン理論の基礎を構築することを狙いこれに取り組んでいる．既知のものとして，Sebo (1987) による Kotzig-Lovasz 分解の T-ジョインアナロジーが知られる．しかしこれは特殊なクラス（因子連結グラフト）を対象としたものであるため，さらなる成果が必要である．

K'17 では Sebo の成果を任意のクラスを対象とするものへと一般化した標準分解を与えた．また，二部グラフトは T-ジョインの標準構造の観点においては，二部コームと呼ばれるグラフトクラスの再帰的な和として捉えられる．これを踏まえ，K'20--21 では二部コームに Dulmage-Mendelsohn 分解のアナロジーとなる標準分解を与えた．さらにこれらの成果を用いて最小 T-ジョイン問題の双対性について新たな知見が得られている（K'22+）．


  1. N. Kita: Parity Factors I: General Kotzig-Lovász decomposition for grafts. arXiv:1712.01920, 2017. 　

  2. N. Kita: Bipartite graft I: Dulmage-Mendelsohn decomposition for combs. arXiv:2007.12943, 2020.　

  3. N. Kita: Bipartite graft II: Cathedral decomposition for combs. arXiv:2101.06678, 2021. 　

  4. N. Kita: Constructive characterization of critical bipartite grafts. arXiv:2105.11167, 2021. 　

  5. N. Kita: Bipartite graft III: General case. arXiv: 2108. 00245, 2021. 　

  6. N. Kita: Tight cuts in bipartite grafts I: Capital distance components. arXiv:2202.00192, 2022.