Résumé :

A famous result by Dilworth on posets implies that computing a minimum-size path cover (a collection of paths such that every vertex is in some path) of a directed acyclic graph (DAG) is polynomial. Those algorithms have been studied since the 1950s and are still the subject of recent improvements due to applications in fields such as bioinformatics or computational logic. Inspired by the problem of Multi-Robot Path Finding, we translate the problem on temporal graphs, that is, graphs whose arc-set changes over discrete time-steps (we say that a temporal graph is a temporal DAG/tree/etc if the underlying graph, using the union of all arcs that appear, is a DAG/tree/etc). A temporal path, in such a setting, is a path in the underlying (di)graph such that the arcs appear in strictly increasing time-steps (a robot cannot traverse multiple edges at the same time). We are interested in two problems: Temporal Path Cover (TPC), where we aim to simply cover the vertices of the temporal graph using temporal paths; and Temporally Disjoint Path Cover (TD-PC), where we want to cover the vertices with the added condition that two paths cannot occupy the same vertex at the same time, thus representing a partition by using the time-steps as a new dimension allowing paths to use the same vertex at different times (for when robots occupy the whole vertex when traversing it, for example). In both cases, we want to minimize the size of the cover. We prove that the two problems are NP-hard on temporal DAGs, even with strong constraints on both the underlying DAG and the time-steps. However, on temporal trees, while TD-PC remains NP-hard, TPC can be solved in polynomial-time. This is obtained by creating an auxiliary graph expressing the temporal connectedness of vertices, exhibiting an equivalence between temporal paths in the temporal graph and cliques in the auxiliary graph, and proving that the auxiliary graph is weakly chordal, allowing us to use powerful algorithms from the literature. Both problems are also polynomial-time solvable on temporal rooted directed trees and temporal lines, which is not the case of all problems on temporal graphs (such as Linkage). We also give an XP algorithm for TPC and an FPT algorithm for TD-PC, both parameterized by the treewidth plus the total number of time-steps. On the structural side, we discuss on when a temporal analogue of Dilworth's theorem holds in the classes that we study.