Algorithm for detecting and removing the least amount of conflicting facts (perhaps in PROLOG)?

Question

How do you program the following algorithm?

Imagine a list of "facts" like this one, where letters represent variables associated with numerical values:

x = 1 y = 2 z = 3 a = 1 b = 2 c = 3 a = x b = z c = z 

These “facts” obviously should not be “true”: it is impossible for b = z, when b = 2 and z = 3. If either b = z or b = 2 were deleted, all the facts would be consistent. If z = 3 and either b = z or c = z were deleted, then all the facts would be consistent, but there would be less fact than indicated above. This set contains many such consistent subsets. For example, a = 1, b = 2, c = 3 is a consistent subset, and many others.

Two consecutive subsets are larger than any other consistent subset in this example:

 x = 1 y = 2 z = 3 a = 1 b = 2 c = 3 a = x c = z 

and

 x = 1 y = 2 z = 3 a = 1 c = 3 a = x b = z c = z 

Using the appropriate programming language (I think PROLOG, but maybe I'm wrong), how would you process a large set containing consistent and inconsistent facts, and then output the maximum possible subset of the agreed facts (or a few subsets, as in the example above)?

Answer 1

This is very closely related to the NP-hard multiway cut problem. In the (unweighted) multi-mode section, we have an undirected graph and a set of terminal vertices. The goal is to remove as few edges as possible so that each end vertex is in its own communication component.

For this task, we can interpret each variable and each constant as a vertex, and each equality as an edge from the left side to the right side. Terminal vertices are those associated with constants.

For only two terminals, the problem of multi-channel cutting is the problem of resolving the minimum cut st with polynomial time. We can use minimal cuts to get a polynomial 2-approximation to the multiline cut problem, finding the cheapest cut that separates the two terminals, removing the connected edges and then recursive on the remaining connected components. In the theoretical literature on a multiline section, several approximation algorithms with the best coefficients are proposed.

In practical terms, multi-pass reduction occurs in computer vision applications, so I expect that there has been some work on getting the exact solutions. I do not know what is there, however.

Answer 2

Prolog can be a convenient language for implementation, but some people think about algorithms, which can be a profitable specialized approach.

Among operators of this kind (equality between two variables or between one variable and one constant), the only inconsistency that can arise is the path connecting the two different constants.

Thus, if we find all the inconsistency paths that connect pairs of different constants, it is necessary and sufficient to find a set of edges (initial equalities) that disconnect all these paths.

It is tempting to think that the greedy algorithm here is optimal: always choose the edge to delete, which is common to the largest number of remaining "inconsistent" paths. So I suggest:

1) Find all the simple paths P connecting two different constants (without going through any third constant) and create a connection structure between these paths and their edges.

2) Count the frequencies of the edges E appearing along these "inconsistent" paths P

3) Find a sufficient number of edges to remove by pursuing a greedy strategy, deleting the next edge that appears most often, and accordingly update the edge counts on the remaining paths.

4) Given that the upper bound is on the edges needed for deletion (to leave a consistent subset of operators), apply a backtracking strategy to determine if fewer edges are enough.

---

As applicable to the example in the Question, there are exactly two ways of "inconsistency":

  2 -- b -- z -- 3 2 -- b -- z -- c -- 3 

Removing one of the two edges, 2 -- b or b -- z , common to both of these paths is enough to disable both paths of inconsistency (removing all inconsistencies among other operators).

In addition, it is obvious that for this there would be no other removal of one edge.