Hybrid tractable CSPs which generalize tree structure

(Joint work with Martin Cooper and Peter Jeavons, originally presented at ECAI 2008.)

Satisfiability, Sudoku, graph isomorphism, and conjunctive query evaluation are examples of constraint satisfaction problems (CSPs). Tractable CSPs (those that can be solved in polynomial time) are usually defined by permitting either all possible ways that constraints can interact, or by permitting any constraints to be used to define instances. We introduce the broken-triangle property, which defines a tractable class which allows both interaction and constraints to be restricted, and which significantly generalizes tree interaction structure.

Constraint problems can be solved quickly if a good variable ordering is available, and this is usually found by applying heuristics. Instead, we outline a polynomial time algorithm which finds an ordering of the variables for which the broken-triangle property holds, or determines that no such ordering exists.