Minimizing Reachability Times on Temporal Graphs via Shifting Labels

Minimizing Reachability Times on Temporal Graphs via Shifting Labels

Argyrios Deligkas, Eduard Eiben, George Skretas

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 5333-5340. https://doi.org/10.24963/ijcai.2023/592

We study how we can accelerate the spreading of information in temporal graphs via shifting operations; a problem that captures real-world applications varying from information flows to distribution schedules. In a temporal graph there is a set of fixed vertices and the available connections between them change over time in a predefined manner. We observe that, in some cases, shifting some connections, i.e., advancing or delaying them, can decrease the time required to reach from some vertex (source) to another vertex. We study how we can minimize the maximum time a set of sources needs to reach every vertex, when we are allowed to shift some of the connections. If we restrict the allowed number of changes, we prove that, already for a single source, the problem is NP-hard, and W[2]-hard when parameterized by the number of changes. Then we focus on unconstrained number of changes. We derive a polynomial-time algorithm when there is one source. When there are two sources, we show that the problem becomes NP-hard; on the other hand, we design an FPT algorithm parameterized by the treewidth of the graph plus the lifetime of the optimal solution, that works for any number of sources. Finally, we provide polynomial-time algorithms for several graph classes.
Keywords:
Planning and Scheduling: PS: Theoretical foundations of planning
Agent-based and Multi-agent Systems: MAS: Multi-agent planning
Planning and Scheduling: PS: Scheduling