CODEWITHSUNDEEP
algorithmgraphgrouping
nyanpasu64
nyanpasu64

Reputation: 3145

How to group and merge objects, if some are incompatible with each other?

I have a bunch of objects, which I want to merge into as few composite objects as possible.

I can calculate whether any 2 objects can or cannot be merged, and if they can be merged, merge them.

An object A is incompatible with another B made of N merged objects if and only if A is incompatible with one or more elements of B.

The greedy solution (merge into first which works) fails for 4 objects, where 1x4 (1 can't be grouped with 4), 2x3, 3x4. The greedy solution puts objects 1 and 2 into group 1, then object 3 into group 2, and object 4 into group 3. The correct solution is putting objects 1 and 3 into group 1, and objects 2 and 4 into group 2.

What is the name of the problem, and is it solvable? If so, what's the algorithm?

(Worst case = brute force, which is slow but workable, because I am merging very small numbers of objects.)

Edit: Merging fails if cannot be merged, otherwise merges. Both unmerged and merged are accessible. Takes O(size(a) + size(b)) time and returns an object of size (a+b). Assume size is around 1000.

Upvotes: 2

Views: 380

Answers (1)

Vincent van der Weele
Vincent van der Weele

Reputation: 13187

Consider this as a graph problem. Every object is a vertex, and there is an edge (v1, v2) if and only if v1 and v2 are compatible. You are now looking for a clique cover, which is NP-complete.

Note that the clique cover is a decision problem (is it possible to cover the graph with k cliques?), but you can turn this into an optimization problem by doing a binary search for k (can I cover with, say, 8 cliques? If yes, try 4, if no, try 16, etc). The problem is still NP-complete then.

As @timrau already commented - and as mentioned in the wikipedia link - the complement problem is graph coloring: you have the same vertices, but now there is an edge (v1, v2) if and only if v1 and v2 are incompatible. You then want to find the minimum number of colors needed to color your vertices, such that no adjacent vertices have the same color. Wikipedia also provides a number of algorithms for that.

Upvotes: 3

Related Questions