= Strategic Companies =

<<TableOfContents>>

== Predicates ==

 * '''Input''': produced_by/5, controlled_by/5

 * '''Query''': query/2

 * '''Output''': strategic/1

== 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_1, ..., 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; <<BR>>

 - If O_i is a subset of C', the associated company c_i must belong to C'(for each i=1,...,m). <<BR>>

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

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

 2. each company is controlled by at most four companies. <<BR>>

Under these restrictions the problem is still NP^NP-complete. <<BR>>
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.

Moreover, two distinct companies c_i,c_j in C are provided in input (by means of predicate query), and the existence of a strategic set C' such that c_i and c_j occur in C' has to be checked.

== 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 ground query atom 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). <<BR>>
controlled_by(callipo,star,almera,asdomar,barilla). controlled_by(barilla,callipo,almera,dececco,star). <<BR>>
query(callipo,barilla)?

== Output format ==

If the answer to the input query is positive (i.e., for query(c1,c2), c1 and c2 jointly belong to a minimal strategic set), 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) ==
 * Author:  Mario Alviano 	
   * Affiliation: University of Calabria, Italy
 * Author: Marco Maratea 	
   * Affiliation: University of Genova
 * Author: Francesco Ricca 	
   * Affiliation: University of Calabria, Italy