摘要
无根网络的定向问题在许多情况下被认为是 NP-hard 的。本文介绍了两种算法框架，显著改进了基于网络层次 $l$ 的固定参数可解算法。我们的第一个主要贡献显示，对于多个重要的网络类别，核心算法难点在于寻找网络无向生成器上的有向生成树。通过在 $O(5.3334^l + l)$ 时间内枚举这些生成树，并在多项式时间内定向所有剩余边，我们为基于树的网络解决了定向问题，时间复杂度为 $O(5.3334^l \times n)$，对于果园网络，时间复杂度为 $O(5.3334^l \times n^2)$，其中 $n$ 是图的顶点数量。通过进一步分支扩展此方法，得到针对树子代和普通网络的 $O(10.6667^l \times n^2)$ 时间算法。
我们的第二种技术通过直接猜测生成器上重叠的放置来绕过生成树。这一框架为时间网络、可见重叠和树兄弟网络提供了 $O(12.2071^l \times n^2)$ 的时间算法。最后，我们通过展示即使是计算最小扫描宽度的定向也是关于层次的单指数 FPT，从而证明了重叠猜测框架的多功能性。综上所述，这些结果显著改善了已知的系统发育网络定向的运行时间。
博主点评： 本文针对无根二叉网络的定向问题提出了创新的算法框架，尤其是通过生成器的重叠猜测技术，展示了高效的时间复杂度。这为解决复杂的生物网络问题提供了重要的理论基础和实践指导，值得研究者深入探讨。