A holding owns companies, each of which produces some goods. Moreover, several companies may have joint control over another company. Some of these companies should be sold, under the constraint that all goods can be still produced, and that no company is sold which would still be controlled by the holding after the transaction. A company is *strategic*, if it belongs to a *strategic set*, which is a minimal set of companies satisfying these constraints. Given two companies a and b, the problem is to compute a strategic set containing both a and b, or determine that no such set exists.

In our data sets, we assume that each product is produced by at most two companies and each company is jointly controlled by at most three other companies.

INPUT: Relations "produced_by/3" and "controlled_by/4" given as a a set of ground atoms, and two companies a and b. A fact "produced_by(p,c1,c2)" means that product p is produced by companies c1 and c2; A fact "controlled_by(c,c1,c2,c3)" means that a company c is jointly controlled by companies c1,c2,and c3.

OUTPUT: A strategic set containing both companies a and b, if any; empty set, otherwise.

DATA SETS (two instances for each value 250, 1000, 2500, 6500 and 9500 companies; in each case, the number of products is equal to 3 times the number of companies; the goal is to find a strategic set containing companies 1 and 2)

stratcomp-250.a
stratcomp-250.b

stratcomp-1000.a
stratcomp-1000.b

stratcomp-2500.a
stratcomp-2500.b

stratcomp-6500.a
stratcomp-6500.b

stratcomp-9500.a
stratcomp-9500.b

NOTES:

1. An example encoding for DLV can be found in stratcomp.dl
2. Another example encoding (based on nested application of smodels) can be found in stratcomp.sm2
3. More information: M. Cadoli, T. Eiter, and G. Gottlob. Default Logic as a Query Language. IEEE Transactions on Knowledge and Data Engineering, 9(3):448--4 63, May/June 1997.