ASP Competition 2011: ProblemsDescription/StrategicCompanies

Strategic Companies

Contents

  1. Strategic Companies
    1. Problem Description
    2. Input format
    3. Output format
    4. Example
    5. Author(s)

Problem Description

Strategic companies is a well-known NP^NP-complete problem, which has often been used for systems comparisons, and also in the previous ASP Competitions.

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 for 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 format

An instance of STRATCOMP is modeled by the following facts that will be provided in the input file:

* A set of facts of the form produced_by(p,c1,c2,c3,c4), where produced_by(p,c1,c2,c3,c4) means that product P is produced by companies c1, c2, c3 and c4;

* A set of facts of the form controlled_by(c,c1,c2,c3,c4), where controlled_by(c,c1,c2,c3,c4) means that company c is jointly controlled by c1, c2, c3 and c4;

* A (single) fact of the form query(c1,c2), specifying the query goal: do c1 and c2 belong to a (minimal) strategic set?

For instance:

produced_by(pasta,barilla,amato,dececco,divella). produced_by(tonno,callipo,star,almera,asdomar). controlled_by(callipo,star,almera,asdomar,barilla). controlled_by(barilla,callipo,almera,dececco,star). query(callipo,barilla).

Output format

If 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.

Example

Author(s)

ASP Competition 2011: ProblemsDescription/StrategicCompanies (last edited 2011-01-10 10:36:04 by CarmenSantoro)