← 研踪 PaperTrailarXiv:2611.01569 · v1
A logarithm-free subexponential algorithm for minimum quartet inconsistency
首次提交 2026-11-01 12:51
版本更新 2026-11-01 12:51
雷达观测 2026-11-04 23:43
摘要
We give a deterministic algorithm for complete, unweighted minimum quartet inconsistency (MQI) with time and space $2^{O(k^{1/4})}+n^{O(1)}$, where $n$ is the number of taxa and~$k$ is the allowed number of quartet disagreements. This removes the logarithmic factor from the exponent of the MQI bound announced in 2009. The algorithm combines low-error anchoring, chromatic coding, and dynamic programming that accounts for disagreements with all input quartets, with a refined count of colorings and merging states. We also record a generic ETH-based lower bound. The optimality of the fourth-root exponent remains open.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-01 12:51 · 最新观测版本
A logarithm-free subexponential algorithm for minimum quartet inconsistency
We give a deterministic algorithm for complete, unweighted minimum quartet inconsistency (MQI) with time and space $2^{O(k^{1/4})}+n^{O(1)}$, where $n$ is the number of taxa and~$k$ is the allowed number of quartet disagreements. This removes the logarithmic factor from the exponent of the MQI bound announced in 2009. The algorithm combines low-error anchoring, chromatic coding, and dynamic programming that accounts for disagreements with all input quartets, with a refined count of colorings and merging states. We also record a generic ETH-based lower bound. The optimality of the fourth-root exponent remains open.
查看此版本解读 →查看此版本原文 ↗