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

We survey the use and effect of decomposition-based techniques in qualitative 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 literature, namely, patchwork. As a consequence, we prove that a recently proposed decomposition-based approach that was presented in [AAAI, 2014 ] 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 experimental evaluation of it in a following paper presented in [ICTAI, 2014 ] becomes questionable.