Novel Structural Parameters for Acyclic Planning Using Tree Embeddings
Authors: Christer Bäckström, Peter Jonsson, Sebastian Ordyniak
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce two novel structural parameters for acyclic planning (planning restricted to instances with acyclic causal graphs): up-depth and down-depth. We show that cost-optimal acyclic planning restricted to instances with bounded domain size and bounded upor down-depth can be solved in polynomial time. For example, many of the tractable subclasses based on polytrees are covered by our result. We analyze the parameterized complexity of planning with bounded upand down-depth: in a certain sense, down-depth has better computational properties than up-depth. Finally, we show that computing upand down-depth are fixed-parameter tractable problems, just as many other structural parameters that are used in computer science. |
| Researcher Affiliation | Academia | 1 Department of Computer and Information Science, Link oping University, Sweden 2 Algorithms group, University of Sheffield, UK |
| Pseudocode | No | The paper describes algorithms verbally and through lemmas and theorems but does not contain explicit pseudocode blocks or algorithms labeled as such. |
| Open Source Code | No | The paper does not provide any concrete access to source code, such as a specific repository link or an explicit code release statement. |
| Open Datasets | No | This is a theoretical paper focused on algorithmic complexity and does not involve the use of datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper focused on algorithmic complexity and does not involve the use of datasets or their splits for validation. |
| Hardware Specification | No | This is a theoretical paper and does not discuss experimental hardware specifications. |
| Software Dependencies | No | This is a theoretical paper and does not list any specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | This is a theoretical paper and does not describe any specific experimental setup details such as hyperparameters or training configurations. |