On tree-preserving constraints

Publication Type:
Journal Article
Citation:
Annals of Mathematics and Artificial Intelligence, 2017, 81 (3-4), pp. 241 - 271
Issue Date:
2017-12-01
Full metadata record
Files in This Item:
Filename Description Size
On tree-preserving constraints.pdfPublished Version1.84 MB
Adobe PDF
© 2017, Springer International Publishing Switzerland. The study of tractable subclasses of constraint satisfaction problems is a central topic in constraint solving. Tree convex constraints are extensions of the well-known row convex constraints. Just like the latter, every path-consistent tree convex constraint network is globally consistent. However, it is NP-complete to decide whether a tree convex constraint network has solutions. This paper studies and compares three subclasses of tree convex constraints, which are called chain-, path-, and tree-preserving constraints respectively. The class of tree-preserving constraints strictly contains the subclasses of path-preserving and arc-consistent chain-preserving constraints. We prove that, when enforcing strong path-consistency on a tree-preserving constraint network, in each step, the network remains tree-preserving. This ensures the global consistency of consistent tree-preserving networks after enforcing strong path-consistency, and also guarantees the applicability of the partial path-consistency algorithms to tree-preserving constraint networks, which is usually much more efficient than the path-consistency algorithms for large sparse constraint networks. As an application, we show that the class of tree-preserving constraints is useful in solving the scene labelling problem.
Please use this identifier to cite or link to this item: