The Parameterized Complexity of Motion Planning for Snake-Like Robots
Authors: Siddharth Gupta, Guy Sa'ar, Meirav Zehavi
JAIR 2020 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result is the proof that the Snake Game problem is fixed-parameter tractable (FPT) with respect to k. Specifically, we develop an algorithm that solves Snake Game in time k O(k) n O(1) where n is the number of vertices in the input graph. [...] Our second result is the proof that the Snake Game problem is unlikely to admit a polynomial kernel even on grid graphs. [...] Our last result is a treewidth-reduction procedure for the Snake Game problem. |
| Researcher Affiliation | Academia | Siddharth Gupta EMAIL Guy Sa ar EMAIL Meirav Zehavi EMAIL Ben-Gurion University of the Negev, Israel |
| Pseudocode | Yes | Algorithm 1: Construction of a (k 1)-sparse configuration graph. Algorithm 2: Construction of a generalized (k 1)-sparse configuration graph. Algorithm 3: Tr Red Alg Iter Algorithm 4: Tr Red Alg |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code or links to code repositories. |
| Open Datasets | No | This paper is theoretical in nature, focusing on the parameterized complexity of the Snake Game problem. It does not describe experiments using datasets. |
| Dataset Splits | No | This paper is theoretical in nature, focusing on the parameterized complexity of the Snake Game problem. It does not describe experiments using datasets, and therefore no dataset splits are provided. |
| Hardware Specification | No | The paper does not describe any specific hardware used for running experiments, as the work is theoretical in complexity analysis and algorithm design. Table 1 provides a theoretical running time comparison rather than experimental benchmarks. |
| Software Dependencies | No | This paper describes theoretical algorithms and complexity analysis. It does not specify any software dependencies or versions used for implementation. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and complexity analysis rather than empirical experiments. Therefore, there are no experimental setup details, hyperparameters, or training configurations described. |