Seminar Announcement
Date: Wednesday, 17 January 2024
Time: 3:30 PM
Venue: Lecture Hall 1
Covering a graph using shortest paths
Florent Foucaud
Universitaire des Cézeaux, France.
17-01-24

---

Abstract

We discuss some recent developments around the problem of covering (the vertices of) a graph using a minimum number of shortest paths (without prescribed endpoints), called the ISOMETRIC PATH COVER problem. We will present a simple hardness result, a constant-factor approximation algorithm for some graph classes including chordal graphs (that can be extended to hyperbolic graphs and other classes), and an interesting relation between the solution size and the tree-width of the graph. The latter leads to an XP algorithm when we parameterize the problem by the solution size. We may also discuss related problems, depending on time.

The talk is based on joint work from several recent papers: https://hal.archives-ouvertes.fr/hal-03899912 (ISAAC 2022) https://arxiv.org/abs/2206.15088 (ISAAC 2022 / Algorithmica) https://arxiv.org/abs/2212.11653 (CIAC 2023