TY - GEN
T1 - A characterisation of the complexity of forbidding subproblems in binary max-CSP
AU - Cooper, Martin C.
AU - Escamocher, Guillaume
AU - Živný, Stanislav
PY - 2012
Y1 - 2012
N2 - Tractable classes of binary CSP and binary Max-CSP have recently been discovered by studying classes of instances defined by excluding subproblems. In this paper we characterise the complexity of all classes of binary Max-CSP instances defined by forbidding a single subproblem. In the resulting dichotomy, the only non-trivial tractable class defined by a forbidden subproblem corresponds to the set of instances satisfying the so-called joint-winner property.
AB - Tractable classes of binary CSP and binary Max-CSP have recently been discovered by studying classes of instances defined by excluding subproblems. In this paper we characterise the complexity of all classes of binary Max-CSP instances defined by forbidding a single subproblem. In the resulting dichotomy, the only non-trivial tractable class defined by a forbidden subproblem corresponds to the set of instances satisfying the so-called joint-winner property.
UR - https://www.scopus.com/pages/publications/84868281649
U2 - 10.1007/978-3-642-33558-7_21
DO - 10.1007/978-3-642-33558-7_21
M3 - Conference proceeding
AN - SCOPUS:84868281649
SN - 9783642335570
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 265
EP - 273
BT - Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings
T2 - 18th International Conference on Principles and Practice of Constraint Programming, CP 2012
Y2 - 8 October 2012 through 12 October 2012
ER -