Locally Rainbow Paths
Authors: Till Fluschnik, Leon Kellerhals, Malte Renken
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that the problem is computationally intractable even if r = 2 or if one looks for a locally rainbow among the shortest paths. On the positive side, if one looks for a path that takes only a short detour (i.e., it is slightly longer than the shortest path) and if r is small, the problem can be solved efficiently. Indeed, the running time of the respective algorithm is near-optimal unless the ETH fails. Our contributions. We study the parameterized complexity of LOCALLY RAINBOW WALK and LOCALLY RAINBOW PATH, with a focus on the locality parameter r. We show that the path variant is NP-hard for any fixed value of r 2 (Theorem 16). In contrast, we are able to design an algorithm with running time 2O(r log r) n O(1) for the walk variant (Theorem 1), with n being the number of vertices. This result is achieved by developing an ordered version of the representative families technique. We prove this result to be optimal in the sense that no 2o(r log r) n O(1)-time algorithm is possible if the ETH holds (Theorem 12). |
| Researcher Affiliation | Academia | Till Fluschnik1, Leon Kellerhals2, Malte Renken2 1Institut für Informatik, TU Clausthal, Germany 2Technische Universität Berlin, Algorithmics and Computational Complexity, Germany till.fluschnik@tu-clausthal.de, leon.kellerhals@tu-berlin.de, m.renken@tu-berlin.de |
| Pseudocode | Yes | Algorithm 1. Set c W0 s := {(c(s))} and for all v V (G) \ {s}, set c W0 v := . Algorithm 2. Set b R0 s := {(c(s))} and b R0 v := for all v V (G) \ {s}. |
| Open Source Code | No | The paper does not mention providing any source code for the described methodology. |
| Open Datasets | No | This is a theoretical computer science paper. It does not involve empirical studies, datasets, or model training. |
| Dataset Splits | No | This is a theoretical computer science paper. It does not involve dataset splits for empirical validation. |
| Hardware Specification | No | As a theoretical computer science paper, it does not describe any experimental setups that would require hardware specifications. |
| Software Dependencies | No | The paper describes algorithms and proofs, not software implementations with specific dependencies and version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not describe any empirical experimental setup with hyperparameters or training configurations. |