Toward a radical extension of matroidal optimization theory

拟阵优化理论的根本扩展

• 批准号: 18K13451
• 负责人: 喜多 奈々緒
• 金额: $ 2.66万
• 依托单位: Tokyo University of Science
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-04-01 至 2023-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-18K13451/
• 关键词: 離散数学; 組合せ最適化; アルゴリズム; グラフ; ネットワーク; パリティ因子; 標準分解; グラフ理論; 離散最適化; マッチング理論; 離散数理

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

今年，我们在总结上一年成果的同时，能够把平价因子往我们原来没有规划的方向发展。奇偶因子（T 联接）是组合学中的一个经典主题，对应于最大匹配问题的变体，该问题被认为是多项式可解类的核心。最小奇偶校验因子问题是多项式时间可解的，具有类似于匹配的属性。另一方面，奇偶因子表现出比匹配更复杂的属性，并且与许多未解决的问题相关，使它们成为研究多项式可解性本质的独特而有趣的目标。去年，我们将二部图的 Dulmage-Mendelsohn (DM) 分解（匹配的标准分解之一）推广为奇偶因子定理。该结果今年以单作者论文形式撰写，并发布在开放获取存储库上。然而，后来的考虑表明，DM 分解方法不足以理解奇偶校验因子的结构，因此我们致力于推导提供成分表征的标准分解，我们获得了奇偶校验因子的二部大教堂分解。大教堂分解最初是一种标准分解，描述非二分图中的匹配结构。然而，在理解二分图中奇偶校验因子的结构时，我们发现类似大教堂分解结构的二分和奇偶校验因子类比提供了充分描述该结构的标准分解。此外，这一结果为迄今为止尚不清楚的DM分解和大教堂分解之间的关系提供了新的认识。该结果被编译为单人论文并发布在开放获取存储库上。此外，我们目前正在撰写另外两篇与耳朵分解相关的论文，这些论文是与该结果相关的，预计很快就会发表。

项目成果

Constructive Characterization of Critical Bidirected Graphs

关键双向图的建设性表征

• 发表时间: 2019
• 作者: Hidesato Kuroki;Kohei Soga;喜多 奈々緒;足立真訓;Sasaki Takiko;Masanori Adachi;Kohei Soga;喜多 奈々緒;Y. Kiriu and D.A. Mejia;喜多 奈々緒;Nanao Kita
• 通讯作者: Nanao Kita

非二部的 Dulmage-Mendelsohn 分解と Berge 双対の束構造

非二部 Dulmage-Mendelsohn 分解和 Berge 对偶丛结构

• 发表时间: 2018
• 作者: 村田 笑菜 ; 佐々木 多希子 ; 友枝 明保;喜多 奈々緒;M. Cardona and D.A. Mejia;Masanori Adachi;喜多 奈々緒
• 通讯作者: 喜多 奈々緒

Nonbipartite Dulmage-Mendelsohn Decomposition for Berge Duality

Berge 对偶性的非二部 Dulmage-Mendelsohn 分解

• DOI: 10.1007/978-3-319-94776-1_25
• 发表时间: 2018
• 期刊: ecture Notes in Computer Science
• 作者: Miguel Cardona;Lukas Klausner;Diego A. Mejia;足立真訓;Nanao Kita
• 通讯作者: Nanao Kita

二部グラフにおけるパリティ因子のためのカテドラル標準分解

二部图中奇偶校验因子的大教堂标准分解

• 发表时间: 2020
• 作者: Hidesato Kuroki;Kohei Soga;喜多 奈々緒;足立真訓;Sasaki Takiko;Masanori Adachi;Kohei Soga;喜多 奈々緒
• 通讯作者: 喜多 奈々緒

双向臨界グラフの構成的特徴づけ

双向临界图的建设性表征

• 发表时间: 2019
• 作者: Hidesato Kuroki;Kohei Soga;喜多 奈々緒;足立真訓;Sasaki Takiko;Masanori Adachi;Kohei Soga;喜多 奈々緒;Y. Kiriu and D.A. Mejia;喜多 奈々緒;Nanao Kita;喜多 奈々緒
• 通讯作者: 喜多 奈々緒