On graphs coverable by k shortest paths

Speaker(s)

Maël Dumas

Language of the talk

English

Date

Oct. 25, 2024, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

We show that if the edges or vertices of an undirected graph G can be covered by k shortest paths, then the pathwidth of G is upper-bounded by a single exponential function of k. As a corollary, we prove that the problem Isometric Path Cover with Terminals (which, given a graph G and a set of k pairs of vertices called terminals, asks whether G can be covered by k shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. Moreover, this implies that the related problem Isometric Path Cover (defined similarly but where the set of terminals is not part of the input) is in XP with respect to parameter k.
This a joint work with Florent Foucaud, Anthony Perez and Ioan Todinca.

---