Tractable Classes of Binary CSPs Defined by Excluded Topological Minors

Cohen, David A.; Cooper, Martin C.; Jeavons, Peter; Zivný, Stanislav

Tractable Classes of Binary CSPs Defined by Excluded Topological Minors

David A. Cohen, Martin C. Cooper, Peter Jeavons, Stanislav Zivný

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 1945-1950.

Abstract

The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variables. A CSP instance can be presented as a labelled graph (called the microstructure) encoding both the forms of the constraints and where they are imposed. We consider subproblems defined by restricting the allowed form of the microstructure. One form of restriction that has previously been considered is to forbid certain specified substructures (patterns). This captures some tractable classes of the CSP, but does not capture the well-known property of acyclicity. 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.

David A. Cohen, Martin C. Cooper, Peter Jeavons, and Stanislav Zivný. 2015. Tractable Classes of Binary CSPs Defined by Excluded Topological Minors. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 1945–1950. https://ijcai.org/proceedings/2015/276

@inproceedings{ijcai2015p276,
  title     = {Tractable Classes of Binary CSPs Defined by Excluded Topological Minors},
  author    = {Cohen, David A. and Cooper, Martin C. and Jeavons, Peter and Zivný, Stanislav},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {1945--1950},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/276},
}

TY  - CPAPER
TI  - Tractable Classes of Binary CSPs Defined by Excluded Topological Minors
AU  - Cohen, David A.
AU  - Cooper, Martin C.
AU  - Jeavons, Peter
AU  - Zivný, Stanislav
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 1945
EP  - 1950
UR  - https://ijcai.org/proceedings/2015/276
ER  -