Local search for CSPs

A popular local search being used in CSP is Min-conflicts heuristic.

The structure of problems

There are some smart ways to re-structure a big CSP problem into independant subproblems $\mathit{CSP}_i$ , so that the overall complexity could be reduced significantly.

Tree CSP solver

#∆

How can independence be ascertained?:: By finding connected components of the constraint graph.

(Review note: this appears banal now)

What is the computation complexity of a CSP problem if it is divisible to $n/c$ subproblems? (with $n$ is the size of the original problem, $c$ is the size of the subproblem):: $O(d^cn/c)$

What is the notion of consistency where CSP's constraint graph is actually a tree?:: directed arc consistency or DAC

What is the name of the sort that turn a graph into a tree (if possible)?:: topological sort

What are the two primary approaches to "reduce" a constraint graphs to trees?:: By remove nodes or collapsing nodes together.

(But what are the strategy to select node to remove or collapse?)