After a few too many days immersed in the popular entrepreneurial self-help book Mine Your...

After a few too many days immersed in the popular entrepreneurial self-help book Mine Your Own Business, you ve come to the realization that you need to upgrade your office computing system. This, however, leads to some tricky problems.

In configuring your new system, there are k components that must be selected: the operating system, the text editing software, the e-mail program, and so forth; each is a separate component. For the jth component of the system, you have a set Aj of options; and a configuration of the system consists of a selection of one element from each of the sets of options A1, A2,..., Ak.

Now the trouble arises because certain pairs of options from different sets may not be compatible. We say that option xt e At and option Xj e Aj form an incompatible pair if a single system cannot contain them both. (For example, Linux (as an option for the operating system) and Microsoft Word (as an option for the text-editing software) form an incompatible pair.) We say that a configuration of the system is fully compatible if it consists of elements x1 ε A1, x2 ε A2,...xk ε Ak such that none of the pairs (xi, xj) is an incompatible pair.

We can now define the Fully Compatible Configuration (FCC) Problem. An instance of FCC consists of disjoint sets of options A1, A2,Ak, and a set P of incompatible pairs (x, y), where x and y are elements of different sets of options. The problem is to decide whether there exists a fully compatible configuration: a selection of an element from each option set so that no pair of selected elements belongs to the set P.

Example. Suppose k = 3, and the sets A1, A2, A3 denote options for the operating system, the text-editing software, and the e-mail program, respectively. We have

A1 = {Linux, Windows NT},

A2 = {emacs, Word},

A3 = {Outlook, Eudora, rmail},

with the set of incompatible pairs equal to

P = {(Linux, Word), (Linux, Outlook), (Word, rmail)}.

Then the answer to the decision problem in this instance of FCC is yes–for example, the hoices Linux e A1, emacs e A2, rmail e A3 is a fully compatible configuration according to the definitions above.

Prove that Fully Compatible Configuration is NP-complete.