Optimizing Reachability Sets in Temporal Graphs by Delaying
Authors: Argyrios Deligkas, Igor Potapov9810-9817
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide a thorough investigation of the computational complexity of different objectives related to reachability sets when these operations are used. For the merging operation, we prove NP-hardness results for several minimization and maximization reachability objectives, even for very simple graph structures. For the second operation, we prove that the minimization problems are NP-hard when the number of allowed delays is bounded. We complement this with a polynomial-time algorithm for the case of unbounded delays. and Theorem 7 Algorithm 6 is optimal for MINREACH, MINMAXREACH, MINAVGREACH under δ DELAYING. |
| Researcher Affiliation | Academia | Argyrios Deligkas, Igor Potapov University of Liverpool {argyrios.deligkas, potapov}@liverpool.ac.uk |
| Pseudocode | Yes | Figure 6: Algorithm for δ DELAYING. |
| Open Source Code | No | The paper does not contain any statement about making its source code available or provide a link to a code repository. |
| Open Datasets | No | The paper focuses on theoretical computational complexity results and algorithm design, and does not report on experiments conducted using datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and focuses on computational complexity and algorithm design, thus no hardware specifications for experiments are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on computational complexity and algorithm design; therefore, it does not specify software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments or their setup, thus no hyperparameter values or training settings are provided. |