Recently, we were informed by Michael Sioutis, a former member of our
group, about a flaw in the partitioning algorithm that we employ in our
paper presented at the AAAI'14 conference "Fast consistency checking of
very large real-world RCC-8 constraint networks using graph partitioning"
that makes our developed consistency algorithm incomplete and not sound
for particular input networks and computed k-way partitionings. In
particular, the problem appears in Algorithm 1 (PartGraph algorithm) of
the paper and affects the soundness and completeness of Algorithm 2
(D-Consistency algorithm). We thank Michael Sioutis for this observation.

The above deficiency arises in the following case. First, suppose that a
k-way partitioning of a constraint network has been computed. The problem
appears when there are crossing edges participating in a cycle that is
spread among two or more parts of the k-way partitioning and these
crossing edges are not assigned collectively to the same part by the
employed heuristics of the PartGraph algorithm. Breaking such cycles has
as a side effect the ignorance of some constraints during consistency
checking. The fix is to identify and maintain such cycles during
execution of the PartGraph algorithm.

The above case is more likely to emerge in dense networks and networks
containing many cycles. Furthermore, it also depends on the computed 
k-way partitioning and the number of the parts k. As the number of k
increases, such cases become much more frequent. Thus, although PartGraph
does not provide for that case, it is not always the case that the k-way
partitioning computed in combination with the heuristics of PartGraph
for distributing the crossing edges, will finally lead to a flawed
partitioning.

With respect to the empirical evaluation of the paper, all decisions
made for the consistency of the input networks are correct and in line
with the rest of the reasoners against which our reasoner was compared.
Consequently, there are not cases in which our reasoner reports an input
network as consistent, whereas it should have been reported as
inconsistent. If there was such a case, our reasoner would have indeed
been reported to perform far better than the other reasoners, since it
would not explore the whole search space. This particular case would
have dramatically affected the reported timings and distorted
qualitatively the results of our evaluation.

We will fix the above flaw in a subsequent extended version of this
paper.