Toward a radical extension of matroidal optimization theory

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

本年度には，前年度の成果をまとめる中で，パリティ因子に関して当初予定していなかった方向への発展を得た．パリティ因子（T-ジョイン）は，組合せ論の古典的なトピックであり，多項式可解クラスの中核に座すとされる最大マッチング問題の亜種に相当する．最小パリティ因子問題は，マッチングと類似の性質を持つ多項式時間可解である．その一方で，パリティ因子は，マッチングに比してずっと複雑な性質を呈し，また多くの未解決問題と関連するため，多項式可解性の本質を追究する上で特異かつ興味深い対象である．前年度には，マッチングに関する標準分解の一つである，二部グラフのDulmage-Mendelsohn (DM) 分解を，パリティ因子のための定理へと一般化したものを導出した．この成果については，本年度に単著論文として執筆し，オープンアクセスレポジトリにて公開した．しかし，パリティ因子の構造を把握するにはDM分解的な構造把握では不十分であることがその後の考察により明らかになったため，構成的特徴付けを与える標準分解の導出に取り組み，そのようなものとしてパリティ因子の二部的カテドラル分解を得た．カテドラル分解とは本来非二部グラフにおけるマッチングの構造を記述する標準分解である．しかし，二部グラフにおけるパリティ因子の構造を把握するにあたっては，カテドラル分解的な構造の二部的かつパリティ因子アナロジーによって十分な構造を記述する標準分解が与えられることが判った．さらにこの成果により，これまで不明であったDM分解とカテドラル分解の関係について一つの理解が得られた．この成果については単著論文として取りまとめオープンアクセスレポジトリに公開した．また，この成果に関連して得られた，耳分解などに関するさらに2本の論文を執筆中であり，近日中に公開する予定である．