Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems
Authors: Hubie Chen, Georg Gottlob, Matthias Lanzinger, Reinhard Pichler
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give a characterization of those classes of CSPs for which the problem becomes fixedparameter tractable. Our characterization significantly increases the utility of the CSP framework by making it possible to decide the fixed-parameter tractability of problems via their CSP formulations. Our proof of the theorem relies on two central lemmas. |
| Researcher Affiliation | Academia | 1Birkbeck, University of London 2Oxford University 3TU Wien h.chen@dcs.bbk.ac.uk, georg.gottlob@cs.ox.ac.uk, {mlanzing, pichler}@dbai.tuwien.ac.at |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | This paper is theoretical and does not describe experiments involving datasets for training or evaluation. |
| Dataset Splits | No | This paper is theoretical and does not involve data splits for training, validation, or testing. |
| Hardware Specification | No | This paper is theoretical and does not describe the hardware used for any experiments. |
| Software Dependencies | No | This paper is theoretical and does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |