Strategic Companies

Problem Description

Strategic companies is a well-known NP^NP-complete problem that has often been used for systems comparisons, and also in the previous ASP Competitions. In the Strategic Companies problem, a collection C = c₁, ..., c_m of companies is given, for some m >= 1. Each company produces some goods in a set G, and each company c_i in C is possibly controlled by a set of owner companies O_i (where O_i is a subset of C, for each i = 1,...,m). In this context, a set C' of companies (i.e., a subset of C) is a "strategic set" if it is minimal among all the sets satisfying the following conditions:

• Companies in C' produce all goods in G;

• If Oi is a subset of C', the associated company ci must belong to C'(for each i=1,...,m).
  

In our setting, instances are subject to two additional restrictions:

1. each product is produced by at most four companies; and

2. each company is controlled by at most four companies.
   

Under these restrictions the problem is still NP^NP-complete.

Instances of strategic companies are encoded by means of the predicates produced_by and controlled_by. In particular, there is a fact producedBy(p,c1,c2,c3,c4) when a product p is produced by companies c1, c2, c3 and c4, and a fact controlledBy(c,c1,c2,c3,c4) when a company c is controlled by companies c1, c2, c3 and c4. If a product p is produced by less than four companies (but at least one), the atom produced_by(p,c_a,c_b,c_c,c_d) contains repetitions of companies. For instance, producedBy(p,c_a,c_b,c_c,c_c) is used for representing that p is produced solely by c_a, c_b, and c_c. Analogously, if a company c is controlled by less than four companies.

The goal of the problem is a follows: Given two distinct companies c_i,c_j in C, we ask for checking whether no strategic set C' containing both c_i and c_j does exist. Queries of this benchmark have thus to be answered cautiously.

Predicates

• Input: produced_by/5, controlled_by/5, strategic_pair/2, non_strategic_pair/2

• Output: yes or no

Input format

An instance of Strategic Companies 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 c₁, c₂, c₃ and c₄;

  - 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 c₁, c₂, c₃ and c₄;

  - A ground query of the form non_strategic_pair(c1,c2)?, specifying the query goal, i.e., whether no strategic set containing both c₁ and c₂ does exist.

For instance:

produced_by(pasta,barilla,dececco,dececco,dececco).
produced_by(tonno,callipo,star,star,star).
controlled_by(barilla,star,star,star,star).
controlled_by(dececco,barilla,barilla,barilla,barilla).
non_strategic_pair(barilla,star)?

Output format

The output must be yes or no.

For instance:

no

(Technical details about actual input/output format will be available via the Competition website)

Example(s)

Input:

produced_by(pasta,barilla,dececco,dececco,dececco).
produced_by(tonno,callipo,star,star,star).
controlled_by(barilla,star,star,star,star).
controlled_by(dececco,barilla,barilla,barilla,barilla).
non_strategic_pair(barilla, callipo)?

Output:

yes

Additional sample instances: download

Problem Peculiarities

Type: search/Beyond-NP Competition: both M&S and System competition

This problem is challenging both from the modelling point of view (it is required the availability of constructs allowing an "\exist \forall" quantification over solutions, or some appropriate optimization construct), and from the computational point of view.

Notes and updates

Note that this is a search problem, despite the seemingly presence of a query in input. With respect to former edition of the competition, the output format requires an entire strategic set to be output, and not just the subpart of the set showing that c₁ and c₂ belong to it.

Author(s)

• Author: Mario Alviano
  • Affiliation: University of Calabria, Italy
• Original Authors: Marco Maratea, Francesco Ricca
  • Affiliation: University of Genova and University of Calabria, Italy