Temporal Path Covers: Dilworth Properties and Parameterized Complexity
This work resolves open questions about the parameterized complexity of temporal path cover problems, providing both tractability and hardness results for structural parameters.
The paper shows that Minimum Temporal Path Cover and Minimum Temporally Disjoint Path Cover are polynomial-time solvable under a temporal Dilworth property, with the size equaling the Lovász number of the connectivity graph. It also proves W[1]-hardness for TPC parameterized by deletion distance to linear forest, and gives an FPT algorithm parameterized by vertex cover number plus number of time-steps, while showing NP-hardness for constant vertex cover without time-steps.
The Minimum Temporal Path Cover (TPC) and Minimum Temporally Disjoint Path Cover (TDPC) problems were introduced by [Chakraborty, Dailly, Foucaud, Klasing, MFCS '24]. Both were shown to be NP-hard on temporal DAGs, while the latter is also NP-hard on temporal oriented trees. All tractable cases for T(D)PC established in that paper satisfy a temporal Dilworth property, namely that the size of the minimum T(D)PC is equal to the size of the maximum antichain. This raises a natural question: is T(D)PC polynomial-time solvable under the promise that the respective Dilworth property holds? In this work, we answer this question in the affirmative for both problems, proving in fact that, under the respective promise, the size of the minimum T(D)PC is exactly equal to the Lovász number of the connectivity graph. In another direction, we establish parameterized algorithms and hardness results for TPC and TDPC. Our main result is that TPC is W[1]-hard parameterized by the deletion distance to linear forest even for temporal graphs with two time-steps, answering in the negative an open question by Chakraborty et al. about whether an XP algorithm parameterized by treewidth plus number of time-steps can be improved to FPT. On the other hand, we prove that an FPT algorithm does exist if the vertex cover number is used as parameter instead of the treewidth in the above parameterization. We complement this with a proof that including the number of time-steps in the parameter is necessary to yield tractability, as, otherwise, both TPC and TDPC remain NP-hard even for constant vertex cover size. Along the way, we establish various other para-NP-hardness results involving structural parameters such as the pathwidth and the maximum degree of the underlying graph.