On the speed of constraint propagation and the time complexity of arc consistency testing
作者：
Highlights：
• The time complexity of arc consistency is estimated for any propagation-based algorithm.
• The obtained lower and upper bounds are tight up to a constant factor.
• Examples of slow constraint propagation are analyzed by methods of finite model theory.
摘要
•The time complexity of arc consistency is estimated for any propagation-based algorithm.•The obtained lower and upper bounds are tight up to a constant factor.•Examples of slow constraint propagation are analyzed by methods of finite model theory.
论文关键词：Constraint satisfaction problem,Constraint propagation,Arc consistency,Time complexity,Existential 2-pebble game,Existential-positive two-variable logic
论文评审过程：Received 12 June 2014, Revised 27 August 2017, Accepted 7 September 2017, Available online 19 September 2017, Version of Record 5 October 2017.
论文官网地址：https://doi.org/10.1016/j.jcss.2017.09.003
