摘要
循环秩是由 Eggan 在 1963 年提出的有向图深度参数。Gruber 和 Giannopoulou 等人曾询问，判断给定有向图的循环秩是否不超过 $w$ 是否为固定参数可处理的问题。我们为半完全有向图和有界有向团宽的有向图提供了相应的算法。
具体而言，给定一个 $n$ 个顶点的半完全有向图 $G$ 和一个整数 $w$，我们可以在时间复杂度为 $\mathrm{O}(9^{(w+1)4^{w+2}} \times n^2)$ 的情况下，判断 $G$ 的循环秩是否不超过 $w$。证明归约至有界有向团宽的情况。
我们进一步展示，对于一个具有有向团宽 $k$ 表达式的 $n$ 个顶点的有向图 $G$ 和一个整数 $w$，可以在时间复杂度为 $\mathrm{O}(9^{(w+1) 4^k} \times n)$ 的情况下判断 $G$ 的循环秩是否不超过 $w$。
此外，我们考虑了半完全有向图上的 $\textsc{Minimum Feedback Arc Set}$ 问题，并展示该问题可以在时间复杂度为 $n^{\mathrm{O}(w)}$ 的情况下解决，其中 $w$ 是给定半完全有向图的循环秩。
博主点评： 本文提出的 FPT 算法为处理半完全有向图的循环秩问题提供了新的思路，特别是在有向团宽的限制下，算法的复杂度得到了有效控制。这为相关领域的研究提供了重要的理论基础和实践指导，具有广泛的应用潜力。值得关注的是，如何进一步优化这些算法以应对更复杂的图结构将是未来的研究方向。