June 22, 2026 at 2:30 PM
The Path Cover problem is a fundamental graph algorithmic problem that asks whether the vertices of a given graph G can be covered using a collection of K paths of G. Path Cover contains the celebrated Hamiltonian Path problem as a special case (when k=1). Indeed, when a graph is not Hamiltonian, it is quite fair to ask what is the minimum number of paths required to cover all of its vertices. While it is usual to ask that all the paths in the covering are vertex-disjoint, we here consider the parameterized complexity of the unrestricted version, namely with regard to the Feedback Edge number and the Cluster Vertex Deletion number.
Clara Marcille, ATER à l’École Normale Supérieure de Lyon
AGORA 2, Bâtiment ESPRIT
français
English