離散的対象の上の効率的なアルゴリズム設計の統一的理論構築

点击翻译按钮获取中文摘要

本年度は研究計画のうち基礎となる部分に取り組んだ．まず，既知の結果である「完全マッチングをもつ一般のグラフの標準分解」についてこれを与える既存の証明を見直し整理・簡略化を行った．また，完全マッチングを持つとは限らない場合も含めた一般のグラフに対する標準分解へと拡張し，これらを論文にまとめた．次に，マッチングの一般化の一種として知られている奇ジョインと呼ばれる概念について研究を進めた．より具体的にはKotzig-Lovasz 分解とよばれるマッチング理論の分解型構造定理を一般化し，奇ジョイン版Kotzig-Lovasz 分解を与えることに成功した．奇ジョインはマッチング理論のみならず，最短路問題や多品種流問題など多くの代表的な問題との関連が深いため，この結果自体が今後多くの応用を生み出すことが期待できる．また一方で，一つ目の成果をさらに掘り下げ，マッチング理論と離散最適化分野で重要な概念である劣モジュラ関数との関係を探ることにも取り組んだ．最大マッチング問題の双対問題の最適解は与えられたグラフ上に定義される劣モジュラ関数や，あるいはその一般化の最小化問題の解集合として把握できることが知られている．しかし，これには実質的な対象となるグラフクラスがごく一部に限られているなどの問題がある．これに対し本研究では，この既存の結果における欠点を克服した結果を得るべく，マッチングのグラフ理論的構造を精査することで新たな束論的性質を明らかにした．これによりマッチング理論と劣モジュラ関数の関係を基にした離散最適化の理論展開に新たな発展が期待できる．