Tractable classes of binary CSPs defined by excluded topological minors. / Cohen, David; Cooper, Martin; Jeavons, Peter; Zivny, Stanislav.

2015. 1945-1951 Paper presented at IJCAI, Beijing, China.

Research output: Contribution to conferencePaper

Published

Documents

Abstract

The binary Constraint Satisfaction Problem (CSP)is to decide whether there exists an assignment to aset of variables which satisfies specified constraintsbetween pairs of variables. A CSP instance canbe presented as a labelled graph (called the microstructure)encoding both the forms of the constraintsand where they are imposed. We considersubproblems defined by restricting the allowedform of the microstructure. One form ofrestriction that has previously been considered isto forbid certain specified substructures (patterns).This captures some tractable classes of the CSP,but does not capture the well-known property ofacyclicity. In this paper we introduce the notionof a topological minor of a binary CSP instance.By forbidding certain patterns as topological minorswe obtain a compact mechanism for expressingseveral novel tractable classes, including newgeneralisations of the class of acyclic instances.
Original languageEnglish
Pages1945-1951
Number of pages7
Publication statusPublished - 25 Jul 2015
EventIJCAI - Beijing, China
Duration: 3 Aug 20139 Aug 2013

Conference

ConferenceIJCAI
CountryChina
CityBeijing
Period3/08/139/08/13
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 25182452