Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning

• Published in: Knowledge engineering review 2017, Vol.32, Article e4
• Main Authors: Sioutis, Michael, Salhi, Yakoub, Condotta, Jean-François
• Format: Article
• Language: English
• Subjects: Algebra; Artificial Intelligence; Computer Science; Decomposition; Language; Temporal logic
• ISSN: 0269-8889; 1469-8005
• DOI: 10.1017/S026988891600014X

We survey the use and effect of decomposition-based techniques in qualitative spatial and temporal constraint-based reasoning, and clarify the notions of a tree decomposition, a chordal graph, and a partitioning graph, and their implication with a particular constraint property that has been extensively used in the literature, namely, patchwork. As a consequence, we prove that a recently proposed decomposition-based approach that was presented in the study by Nikolaou and Koubarakis for checking the satisfiability of qualitative spatial constraint networks lacks soundness. Therefore, the approach becomes quite controversial as it does not seem to offer any technical advance at all, while results of an experimental evaluation of it in a following work presented in the study by Sioutis become questionable. Finally, we present a particular tree decomposition that is based on the biconnected components of the constraint graph of a given large network, and show that it allows for cost-free utilization of parallelism for a qualitative constraint language that has patchwork for satisfiable atomic networks.