有向图若每个顶点至多有 $h$ 个非邻居，则称其为 $h$‑半完备。对完全半完备有向图，$k$‑三元组是有向路径宽度有界性的关键障碍，并在多项算法中发挥作用。Fradkin 与 Seymour 在 2013 年证明：若有向路径宽度足够大，则必含一个 $k$‑三元组；他们的构造给出 $f(k)$ 为三指数函数。随后，Kitsunai 等人在 2015 年的工作中将该结论扩展到 $h$‑半完备图，但仅得到存在性证明，且未给出固定参数时间的寻找方法。本文将 $f(k)$ 的上界改进为单指数，并推广到任意 $h$‑半完备图：若有向路径宽度超过 $(h+1)\cdot k\cdot 2^{27k+9}$，则必含 $k$‑三元组，且可在多项式时间内构造。进一步证明，除非指数依赖于 $k$，否则不存在次指数上界；同样，关于 $h$ 的线性下界也是不可避免的。我们还将 Fomin 与 Pilipczuk 的有向路径宽度近似算法扩展到 $h$‑半完备图，使其证书在该类图上仍然有效。相较于 Kitsunai 等人的繁琐分析，我们的证明更简洁；虽然他们的算法是精确的，我们的算法则在多项式时间内给出近似解。作为应用，证明了在 $h$‑半完备图上，弧不相交路径问题在路径数目和 $h$ 两个参数下是固定参数可解的，推广了半完备情形的已知结果。最后展示了有向路径宽度并不控制有向团宽度：对任意 $k$，存在有向路径宽度为 $0$（即无环 $1$‑半完备）的图，其有向团宽度至少为 $k$。
点评