Finding the minimum set of properties that describe a referent in a set of entities

Question

Hello. I was wondering if someone could help me get pointers to solve this problem. A link to algorithms would be great, but pointers to papers/info is also good.

The problem is as follows. Suppose I have a set E of entities E={car1, car2, bicycle} and a set of properties P ={red, blue, small}. I also have a knowledge base such that red(bicycle), blue(car1), blue(car2), small(car2). Suppose I also have a referent r which belongs to E.

The problem consists of finding the minimum set of properties P' \subseteq P such that it unequivocally picks out r from E. Thus, if r is car2, then P'={small}.

Any ideas? I guess something like the set covering problem or functional dependencies (as in DB theory) might provide some insight, but I thought I'd ask before going into that literature. Yet another possibility is building graphs and find algorithms for subgraph isomorphisms... maybe.

Thanks.

Answer 1

First find the set of all properties that r has. Call it S. For each property p in S, find e(p), all the entities that have the property p. It is clear for each p in S that e(p) contains r. Now take the intersections of e(p) for each p in S. If the intersection contains more than one entity, there is no solution, and we end the algorithm.

So we have a set S of properties that uniquely determine the entity r. Now we need to find a minimal subset of S that uniquely determines r. We can remove any property p from S for which there exists a property q in S so that e(p) is a superset of e(q). If you do that exhaustively you will eventually end up with a reduced set of properties T so that the intersection of e(p) for all the p in T will still be {r}, but no further property in T can be removed. This set T is then minimal.

I haven't thought of anything to make finding a property you can remove any more efficient than just trying all combinations, but it seems to me that there should be some way.

Answer 2

You are looking for a minimum set cover of the set E\{r} with negations (complements) of those properties that r belongs to (properties can be treated as subsets of E).

Since these sets can be any sets, this is NP-hard.

More precisely:

Having a set cover instance (U,S) where U is the set that you need to cover and S={s1,s2, ..., sn} is the family of covering sets you can construct an instance of your problem so that its solution gives a set cover in the original problem:

E = U \union {r}, where r is the referent and r does not belong to U. The set of properties P={p1,p2, ..., pn} is constructed from S so that for each e in U and each i such that 1<=i<=n we have pi(e) iff e is not in si. Moreover each property is true for r. In other words properties are complements of the original sets when restricted to U, and r has all properties.

Now it is clear that each set of properties that selects r is a set cover in the original problem - if r is selected by a set S* of properties, then all other elements (that means all those in U) fail at least one property in S*, so every element of U belongs to at least one original set (from construction of properties as complements of the sets). That means that U is union of those sets from which properties in S* were constructed.

The converse is also true - a set cover in U translates to an r-selecting set in E.

The above reduction is obviously polynomial, so the problem is NP-hard.