Tractable classes of binary CSPs defined by excluded topological minors

David Cohen, Martin Cooper, Peter Jeavons, Stanislav Zivny

Research output: Contribution to conferencePaperpeer-review

38 Downloads (Pure)

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
Country/TerritoryChina
CityBeijing
Period3/08/139/08/13

Cite this