Crucially, propagators are for a single constraint only. For a constraint problem, you run all the propagators to a fix point. There is no single global “algorithm” here, and there are no higher level consistencies.
Crucially, propagators are for a single constraint only. For a constraint problem, you run all the propagators to a fix point. There is no single global “algorithm” here, and there are no higher level consistencies.
The arc-consistency to the circuit constraint is NOT about solving Hamiltonian paths. Its about finding all "obviously wrong" assignments that can be discovered looking at 2-variables at a time.
Because all arc-consistency algorithms can be brute-forced by looking at all combinations of pairs of variables, we have at worst O(n^2) number of variables to consider to achieve arc-consistency.
Each variable only has a finite number of assignments (ignoring ILP with infinite numbers: assuming classical constraint programming). Which means that you can brute-force all possibilities in O(n^2 * d^2) where d is the cardinality of the domain, and n is the number of variables.
This means that reaching arc-consistency over the circuit / Hamiltonian path problem is in O(n^2*d^2) worst case (per propagation step. Another O(n) multiplier is added for reaching arc consistency over all variables), with possibly a specialized algorithm that goes faster than that brute force style.
Given a propagator for circuit that reaches domain consistency (note, for the whole n-ary constraint), that is equivalent to a checker of there is a Hamiltonian path and that will most likely never be a polynomial algorithm (unless P=NP). I can’t say that I’m interested in any particular property of the decomposition of the constraint into 2-ary parts, it is not that interesting of a structure. The cool filterings that circuit propagators do are based on global analysis of the whole graph, not on any local property. For example by finding ordering a of strongly connected components in the current graph.
Almost all propagators need to be reasonably fast to be usable, that is sort of a given in this area. An exponential propagator is almost always a bad idea. For all_different there is a O(n^2.5) algorithm for domain consistency which is really cool and important. In practice, the simple value propagation (remove assigned values from the other variables) is often better for finding solutions quickly.
Extending the concept of Arc-consistency out to general n-arity constraints leads to two, ambiguous generalizations. I took one generalization, you seem to have taken the other (because the generalization I took was uninteresting to the problems you are talking about).
I have a strong bias for the practical side of constraint programming systems, as may have come through.