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

函数的图表达性研究

• 批准号: 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凸表現可能性判定問題」に対する多項式時間アルゴリズムの亜種であるとみなせる．つまりこれは，関数のグラフ表現性に関する今までの研究を，計算生物学に応用して得られた成果である．

Phylogenetic tree construction problem is related to the set of four point trees (= the number of leaves = 4 in the phylogenetic tree), and the problem of constructing a phylogenetic tree based on the integration of all trees. Computational biology is the division of theoretical computer science. Phylogenetic tree construction problems are difficult in general, but there are many problems in high speed, approximate and FPT research. One side,"four point tree system (= four point tree set) to the system tree construction problem polynomial time solution" to the natural question to the problem, to the study. The results of this research are introduced into the complete multipartite quartet system, full multipartite quartet system. The new polynomial time can be solved. The results of this study were presented at the International Symposium on Algorithms and Computation (ISAAC'18) in December. This study proposes to solve the problem of determining the probability of quadratic M2 convex performance, which is the result of the previous year. The results of computational biology have been obtained from the study of numerical expression.

项目成果

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

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

• 发表时间: 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

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

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

2次関数のM凸性判定問題

二次函数的 M 凸性确定问题

• 发表时间: 2017
• 作者: Hiroshi Hirai;Yuni Iwamasa;Kazuo Murota;Stanislav Zivny;岩政 勇仁
• 通讯作者: 岩政 勇仁