関数のグラフ表現性に関する研究

函数的图表达性研究

• 批准号: 16J04545
• 负责人: 岩政 勇仁
• 金额: $ 1.22万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2016
• 资助国家: 日本
• 起止时间: 2016-04-22 至 2019-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16J04545/
• 关键词: 組合せ最適化; 離散凸解析; 値付き制約充足問題; グラフ表現性; 系統樹復元

系統樹構築問題とは，与えられた四点木（=葉の数が4の系統樹）の集合に対して，その全てに整合する系統樹を構築する問題である．これは，計算生物学の分野だけでなく，理論計算機科学の分野でも盛んに研究されている問題である．系統樹構築問題は一般的にはNP困難であり，高速なヒューリスティクスアルゴリズム，近似アルゴリズム，FPTアルゴリズムの研究が数多く存在する．一方，「どの四点木システム（＝四点木の集合）に対しては系統樹構築問題が多項式時間で解けるか」という自然な疑問に対しては，ほとんど研究がなされていなかった．本研究の成果として，実社会で現れうる四点木システムを二つ（complete multipartite quartet system, full multipartite quartet system）導入し，それらに対して系統樹構築問題が多項式時間で解けることを示した．これは，新しい多項式時間可解なクラスを明らかにした重要な研究であると言える．この結果は，12月に行われた査読付き国際会議 International Symposium on Algorithms and Computation (ISAAC'18)に採択され，発表を行った．本研究で提案したアルゴリズムは，前年度の成果である「2次M2凸表現可能性判定問題」に対する多項式時間アルゴリズムの亜種であるとみなせる．つまりこれは，関数のグラフ表現性に関する今までの研究を，計算生物学に応用して得られた成果である．

系统发育树构建问题是构建与给定的四点树集（=具有四叶的系统发育树）一致的系统发育树的问题。这是一个不仅在计算生物学领域而且在理论计算机科学领域正在积极研究的问题。系统发育树构建问题一般是NP-hard问题，目前有很多关于快速启发式算法、近似算法和FPT算法的研究。另一方面，对于自然问题“对于哪个四点树系统（=四点树的集合）可以在多项式时间内解决系统发育树构建问题？”的研究很少。作为这项研究的结果，我们引入了现实世界中可以出现的两种四点树系统（完整的多部分四重系统、完全多部分四重系统），并表明它们的系统发育树构建问题可以在多项式时间内解决。这可以说是一项重要的研究，揭示了一个新的多项式时间可解类。这些结果在 12 月举行的同行评审国际会议国际算法与计算研讨会 (ISAAC'18) 上被接受并提交。本研究提出的算法可以被认为是“二次 M2 凸可表示性确定问题”的多项式时间算法的变体，该算法是前一年的结果。换句话说，这是将先前关于函数图表达性的研究应用到计算生物学的结果。

项目成果

完全多部四点木システムからの系統樹構築

从完全多部分四点树系统构建系统发育树

• 发表时间: 2018
• 作者: Hiroshi Hirai;Yuni Iwamasa;Kazuo Murota;Stanislav Zivny;平井 広志，岩政 勇仁
• 通讯作者: 平井 広志，岩政 勇仁

Discrete convexity in binary VCSPs

二元 VCSP 中的离散凸性

• 发表时间: 2018
• 作者: H. Hirai; Y. Iwamasa;K. Murota;S. Zivny
• 通讯作者: S. Zivny

On a general framework for network representability in discrete optimization [Extended Abstract]

离散优化中网络可表示性的通用框架[扩展摘要]

• DOI: 10.1007/978-3-319-45587-7_32
• 发表时间: 2016
• 期刊: Proceedings of the 4th International Symposium on Combinatorial Optimization
• 作者: Hirai Hiroshi;Iwamasa Yuni;Murota Kazuo;Zivny Stanislav;Yuni Iwamasa
• 通讯作者: Yuni Iwamasa

A Tractable Class of Binary VCSPs via M-Convex Intersection

基于M-凸交集的一类可处理的二元VCSP

• DOI: 10.1145/3329862
• 发表时间: 2019
• 期刊: ACM Transactions on Algorithms
• 影响因子: 1.3
• 作者: Hirai Hiroshi;Iwamasa Yuni;Murota Kazuo;Zivny Stanislav
• 通讯作者: Zivny Stanislav

Beyond JWP: A tractable class of binary VCSPs via M-convex intersection

超越 JWP：通过 M 凸交集的一类易于处理的二元 VCSP

• DOI: 10.4230/lipics.stacs.2018.39
• 发表时间: 2018
• 期刊: Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS'18), LIPIcs
• 作者: Hirai Hiroshi;Iwamasa Yuni;Murota Kazuo;Zivny Stanislav
• 通讯作者: Zivny Stanislav