Minimizing Reachability Times on Temporal Graphs via Shifting Labels
Authors: Argyrios Deligkas, Eduard Eiben, George Skretas
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | 1Royal Holloway, University of London 2Hasso Plattner Institute, University of Potsdam {argyrios.deligkas, eduard.eiben}@rhul.ac.uk, georgios.skretas@hpi.de |
| Pseudocode | Yes | Algorithm 1: One Source Reach Fast Algorithm |
| Open Source Code | No | The paper does not include any explicit statement or link indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical evaluation on datasets, thus it does not provide information about dataset availability or access. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation on datasets, thus it does not provide information about training/validation/test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments, thus no specific software dependencies with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, thus no experimental setup details like hyperparameters or training configurations are provided. |