Tractable Classes of Binary CSPs Defined by Excluded Topological Minors
Authors: David A. Cohen, Martin C. Cooper, Peter G Jeavons, Stanislav Zivny
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we introduce the notion of a topological minor of a binary CSP instance. By forbidding certain patterns as topological minors we obtain a compact mechanism for expressing several novel tractable classes, including new generalisations of the class of acyclic instances. |
| Researcher Affiliation | Academia | David A. Cohen Dept. of Computer Science, Royal Holloway, Univ. of London, UK dave@cs.rhul.ac.uk Martin C. Cooper IRIT, Univ. of Toulouse, 31062 Toulouse, France cooper@irit.fr Peter G. Jeavons & Stanislav ˇZivn y Dept. of Computer Science, Univ. of Oxford, UK peter.jeavons@cs.ox.ac.uk standa.zivny@cs.ox.ac.uk |
| Pseudocode | No | The paper presents theoretical definitions, lemmas, propositions, and proofs, but does not include any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper is theoretical and does not mention any open-source code release or provide links to a repository. |
| Open Datasets | No | The paper is purely theoretical and does not use or reference any datasets for training or any other purpose. |
| Dataset Splits | No | The paper is purely theoretical and does not involve empirical validation, thus no training/validation/test splits are mentioned. |
| Hardware Specification | No | The paper is purely theoretical and does not describe any hardware specifications used for experiments. |
| Software Dependencies | No | The paper is purely theoretical and does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is purely theoretical and does not describe any experimental setup details or hyperparameters. |