- FR
- EN
13h45 - 15h15 salle A411
Network interdiction problems deal with the question of how the optimal objective value of an optimization problem on a graph or network (e.g., a shortest path or network flow problem) can be worsened as much as possible by removing a limited number of arcs. These problems represent an important research topic and have a variety of practical applications such as assessing the robustness of critical infrastructure networks or containing the spread of infectious diseases.
In many of these applications, however, the underlying graph is not static, but each arc is active only at a specific point in time. For example, train connections in a passenger transportation network are only available at specified departure times, and in the case of infectious disease spread, contacts between individuals exist only at specific times. The graphs that appear here, where the set of active arcs changes over time, are called temporal graphs in the literature.
In this talk, we connect network interdiction problems and temporal graphs by investigating the interdiction of shortest paths in temporal graphs. The resulting temporal shortest path interdiction problem generalizes one of the most important network interdiction problems to temporal graphs. It studies the question of how to remove a bounded number of arcs from a temporal graph such that the length of a shortest path between two given nodes is maximized. We characterize the complexity of the temporal shortest-path interdiction problem for various natural interpretations of "shortest" paths in temporal graphs (latest start path, earliest arrival path, shortest duration path, shortest traversal path). Although the static shortest path interdiction problem is known to be NP-hard, we obtain polynomial-time algorithms for two of the four problem variants. Finally, we give an outlook on further interesting research topics on network interdiction problems in temporal graphs.
