New Algorithms for Bidirectional Singleton Arc Consistency

Abstract EN

Bidirectional singleton arc consistency (BiSAC) which is an extended singleton arc consistency (SAC) has been proposed recently.

The first contribution of this paper is to propose and prove two theorems of BiSAC theoretically (one is a property of BiSAC and the other is the property of allowing the deletion of some BiSAC-inconsistent values).

Secondly, based on these properties we present two algorithms, denoted by BiSAC-DF and BiSAC-DP, to enforce BiSAC.

Also, we prove their correctness and analyze the space and time complexity of them in detail.

Besides, for special circumstances, we show that BiSAC-DF admits a worst-case time complexity in O(en2d4) and a best one in O(en2d3) when the problem is an already BiSAC, while BiSAC-DP also has the same best one when the tightness is small.

Finally, experiments on a wide range of CSP instances show BiSAC-DF and BiSAC-DP are usually around one order of magnitude faster than the existing BiSAC-1.

For some special instances, BiSAC-DP is about two orders of magnitude efficient.