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

Research output: Contribution to conference › Paper

Published

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

Research output: Contribution to conference › Paper

Cohen, D, Cooper, M, Jeavons, P & Zivny, S 2015, 'Tractable classes of binary CSPs defined by excluded topological minors', Paper presented at IJCAI, Beijing, China, 3/08/13 - 9/08/13 pp. 1945-1951.

Cohen, D., Cooper, M., Jeavons, P., & Zivny, S. (2015). *Tractable classes of binary CSPs defined by excluded topological minors*. 1945-1951. Paper presented at IJCAI, Beijing, China.

Cohen D, Cooper M, Jeavons P, Zivny S. Tractable classes of binary CSPs defined by excluded topological minors. 2015. Paper presented at IJCAI, Beijing, China.

@conference{da540c231b9946269ead5c9d2d01be37,

title = "Tractable classes of binary CSPs defined by excluded topological minors",

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.",

author = "David Cohen and Martin Cooper and Peter Jeavons and Stanislav Zivny",

year = "2015",

month = jul,

day = "25",

language = "English",

pages = "1945--1951",

note = "IJCAI ; Conference date: 03-08-2013 Through 09-08-2013",

}

TY - CONF

T1 - Tractable classes of binary CSPs defined by excluded topological minors

AU - Cohen, David

AU - Cooper, Martin

AU - Jeavons, Peter

AU - Zivny, Stanislav

PY - 2015/7/25

Y1 - 2015/7/25

N2 - 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.

AB - 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.

M3 - Paper

SP - 1945

EP - 1951

T2 - IJCAI

Y2 - 3 August 2013 through 9 August 2013

ER -