Treewidth and Indexicals: Applying Results in Tractability to Propagators

Abstract: I simplify a small part of tractability research in the field of time complexity in constraint programming. Treewidth and strong k-consistency can be combined in order to achieve tractability. The result is partially applied to Extended Indexicals by implementing treewidth in Extended Indexicals. Preliminary tests of the treewidth of the most common constraints have been carried out and the result is promising with the majority of the constraints having a low treewidth.