Poly time reduction Problem: It’s time to upgrade the computing system at your o
ID: 3767677 • Letter: P
Question
Poly time reduction Problem:
It’s time to upgrade the computing system at your ofce. In conguring 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; a conguration ofthe 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 thatoption xi Ai and option xj Aj form an incompatible pair if a single system cannot contain them both. (Forexample, Linux (as an option for the operating system) and Word (as an option for the text-editing software) forman incompatible pair.) We say that a conguration 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 dene the Fully Compatible Conguration (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 conguration: a selection of an element from eachoption 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 editingsoftware, and the e-mail program respectively. We have
A1 = {Linux, Windows},A2 = {vim, Word},A3 = {Outlook, Thunderbird, 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 choices Linux A1,emacs A2, rmail A3 is a fully compatible conguration according to the above denitions.
a. (8 points) Prove that FCC P Independent Set. (Hint: Build a “conict graph,” like we did when reducing
3SAT to Independent Set.)
b. (8 points) Prove that 3SAT P FCC.
c. (8 points) Prove that Fully Compatible Conguration is NP-complete. Use one of the reductions above(from part (a) or (b)) in your proof
Explanation / Answer
e say thatoption xi Ai and option xj Aj form an incompatible pair if a single system cannot contain them both. (Forexample, Linux (as an option for the operating system) and Word (as an option for the text-editing software) forman incompatible pair.) We say that a conguration 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 dene the Fully Compatible Conguration (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 conguration: a selection of an element from eachoption 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 editingsoftware, and the e-mail program respectively. We have
A1 = {Linux, Windows},A2 = {vim, Word},A3 = {Outlook, Thunderbird, 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 choices Linux A1,emacs A2, rmail A3 is a fully compatible conguration according to the above denitions.
a. (8 points) Prove that FCC P Independent Set. (Hint: Build a “conict graph,” like we did when reducing
3SAT to Independent Set.)
b. (8 points) Prove that 3SAT P FCC