I'm not very good at maths, so I'll try to post my question as accurate as possible.
Let's suppose 5 people as a, b, c, d, e, f
Some of them can work together, and some can not. Let's suppose that 'a' can work together with 'b' and 'c' and 'b' can work together with 'd' and 'e'.
I'm writing this rules using the following nomenclature:
{3abc, 3bde}
The first rule means (all 3 of a, b and c can work together) The second rule means (all 3 of b, d and e can work together)
Ok, now suppose than everyone can work together with other two people. The list would be:
3abc, 3abd, 3abe, 3ace... (up to ten combinations)
I'll join together all this rules in a "compressed" form:
3abcde (this means that any combination made of 3 of these 5 people can work together)
Now for the tricky part. Let's suppose that some of the people are mandatory. Using the people a, b, c, d, e and this set of rules
3abc 3abd 3bde
We can see that any of the combinations involves b. Seems that b is important in any of the groups.
I'm going to "compress" this set:
3ABcd, 3bde
The first rule means (3 of abcd but A and B are mandatory, so I capitalize these people) The second rule means (all 3 of bde)
Another examples:
{3acd, 3abe, 3ade, 3bde} --> {3ADce, 3BEad}
I want to find an algorithm to do the compression. I wonder if, given a set of rules, may be more than one optimum compression.
The set of starting rules are all the same size, and preceded by that exact number. I mean, if a rule set is a "magnitude 4" set, all the rules within the set must follow the pattern 4XXXX.
The same letter can't be repeated within the same rule. eg, you can not say 4abca.
Thanks in advance.
Further I shall suppose that we use only comperssion via introducing mandatory people. Then we can interpret (compressed) list of rules of magnitude 2 as a vertex cover of a graph $G$, whose vertices are the people, edges are rules from the initial list, and covering vertices are chosen mandatory persons(if a rule remains uncompressed then we can choose any of its persons as mandatory). In particular, an optimum compression of the initial list corresponds to a minimum vertex cover of the graph $G$. You can read first two sections of the above short Wikipedia article about vertex cover in order that to be acquainted with the complexity of minimum vertex cover for different classes of graphs. For many of them it is hard, so it is unlikely that there is an efficient (that is of polynomial time) algorithm to solve it exactly. There exists an effective approximation algorithm of factor $2$ but it cannot be approximated within a factor of 1.3606 for any sufficiently large vertex degree unless P = NP. Moreover, if the unique games conjecture is true then minimum vertex cover cannot be approximated within any constant factor better than 2.