摘要
最小时间路径覆盖（TPC）和最小时间不相交路径覆盖（TDPC）问题由 [Chakraborty 等, MFCS '24] 提出。这两个问题在时间有向无环图（DAG）上被证明是 NP-hard 的，而后者在时间有向树上同样是 NP-hard 的。文章中确立的所有可解情况都满足时间 Dilworth 性质，即最小 T(D)PC 的大小等于最大反链的大小。这引出了一个自然问题：在满足相应的 Dilworth 性质的前提下，T(D)PC 是否可以在多项式时间内解决？
在本研究中，我们对这两个问题给出了肯定的答案，实际上证明了在满足相应前提下，最小 T(D)PC 的大小正好等于连通图的 Lovász 数。
此外，我们还建立了 TPC 和 TDPC 的参数化算法和难度结果。我们的主要结果是 TPC 在删除距离为线性森林的情况下是 W[1]-hard，即使对于只有两个时间步的时间图，这否定了 Chakraborty 等人提出的一个开放问题，即是否可以通过树宽加时间步数的参数化来改进 XP 算法。另一方面，我们证明了如果使用顶点覆盖数作为参数，则存在一个 FPT 算法。我们还证明了在参数中包含时间步数是实现可解性的必要条件，因为如果不包含，TPC 和 TDPC 即使在常数顶点覆盖大小下也仍然是 NP-hard 的。
在此过程中，我们还确立了与结构参数（如路径宽度和底层图的最大度数）相关的各种其他 para-NP-hardness 结果。
博主点评： 本文深入探讨了时间路径覆盖的复杂性，尤其是参数化算法的应用，为理解时间图中的路径覆盖问题提供了重要的理论支持。研究结果不仅丰富了图论的应用，还为未来的算法设计指明了方向。