|
|
 |
|
Jeudi 27 Mars
| Heure: |
10:30 - 11:30 |
| Lieu: |
Salle C213 |
| Résumé: |
Fine-grained complexity of reachability problems on different temporal graph models |
| Description: |
Guillaume Aubian Temporal graphs model interactions evolving over time, with different representations depending on how time is taken into account: several models coexist, notably the point model and the interval model. Although these two models are often considered equivalent in discrete time, switching from one to the other can have major implications in terms of computational complexity. In this talk, I'll describe how we proved fundamental complexity discrepancies between these two models for classical problems such as computing the fastest time path (minimizing the total travel time) and the shortest time path (minimizing the number of edges). I will also explain how, while the computation of the fastest time path can be solved in quasi-linear time in the point model, it requires quadratic time in the interval model under standard complexity assumptions. However, a quasi-linear time algorithm exists in the interval model with zero path times. Interestingly, we found no such discrepancy for the global temporal connectivity problem, for which we proved a valid quadratic lower bound in both models, corresponding to the known upper bounds. These results shed new light on the computational limits of temporal graphs and the impact of the choice of time representation. This is joint work with Filippo Brunelli, Feodor F. Dragan, Guillaume Ducoffe, Michel Habib, Allen Ibiapina and Laurent Viennot. |
|
|
