» ASP Competition | |
|
Strategic CompaniesProblem descriptionStrategic companies is a $\SigmaP{2}$-complete problem, which is well-known in the literature, it has been often used for systems comparisons, and also in the ASP'07 Competition.A holding owns companies C(1),...,C(c), each of which produces some goods. Some of these companies may jointly control another one. Suppose that some companies should be sold under the constraint that all goods can still be produced, and that no company is sold which would still be controlled by the holding afterwards. A company is strategic, if it belongs to some *strategic set*, which is a (subset) minimal set of companies satisfying these constraints. The problem amounts to checking whether some given companies are strategic. We consider a particular setting in which each product is produced by at most four companies and each company is jointly controlled by at most four companies. And we ask whether two given companies are strategic, that is, if they belong to the same (minimal) strategic set. Input formatAn instance of STRATCOMP is modeled by the following facts that will be provided in the input file:
For instance: Output FormatIf the answer to a query, e.g., query(c1,c2), is positive (i.e. c1 and c2 jointly belong to a (minimal) strategic set), then the output must contain a number of ground atoms of the form strategic(i) (where "strategic(i)" stands for "company i is strategic") witnessing that c1 and c2 belong to a strategic set.Authors: Mario Alviano, Marco Maratea and Francesco Ricca |