Communications of the ACM
Last Byte
Maximal Cocktails
Credit: Getty Images
Orphan diseases are ones that affect very few people. For that reason, there may be no drugs specifically aimed at them, so one tries cocktails of drugs designed for other related diseases. One difficulty with cocktails is that drugs can interact badly. On the other hand, if drugs do not interact badly there is no reason not to try them together in the hopes of gaining a synergistic effect.
Mathematically, the drugs are nodes and harmful interactions are edges between drugs. Given such an undirected graph, the goal to find all maximal cocktails, which correspond to maximum independent sets.
We will count how many there are and what happens if new interactions are discovered.
Warm-Up: If there are four drugs 1, 2, 3, 4 and only 1 and 2 have a bad interaction, then what are the maximal cocktails?
Solution to Warm-Up: {1, 3, 4} and {2, 3, 4}.
Warm-Up: In the setting of the previous problem, would adding an edge between 3 and 4 increase or decrease the number of maximal cocktails?
Solution to Warm-Up 2: Increase, because now we would have {1, 3}, {1, 4}, {2, 3}, {2,4}.
Question: If we add another edge beyond 1—2 and 3—4, will we have more or fewer maximal cocktails?
Solution: All such edges would give a result that is isomorphic to 1—2—3—4 That gives maximal sets {1, 3}, {1, 4}, {2, 4}, leaving only three maximal cocktails.
So sometimes adding an edge increases the number of maximal cocktails and sometimes it decreases that number. For example, adding the single edge 1—4 to 1—2—3—4 will give maximal cocktails: {1, 3}, {2, 4}.
Figure. Drugs 1 and 2 should never be given together. Drugs 3 and 4 also interact badly. Which maximal distinct cocktails of drugs can be given while avoiding bad drug interactions?
On the other hand, adding 1—3, 1—4, and 2—4 to 1—2—3—4 yields a clique among these four drugs. The resulting maximal cocktails are {1},{2},{3}, {4}. End of solution.
Question: Can you find an edge configuration that will yield 18 maximal cocktails for eight drugs?
Solution: Here is one (due to my colleague Joel Spencer):
1—2—3—1
4—5—6—4
7—8
The maximal cocktails would consist of one drug from {1, 2, 3}, one from {4, 5, 6}, and one from {7,8}. So this is 3 * 3 * 2 = 18 maximal independent sets. I conjecture no more are possible. End of solution.
The last problem suggests the following conjecture, which might be fun to attempt to prove: The number of maximal cocktails is the product of the maximal cocktails of each connected component.
Upstart 1: Consider a game in which the players use some random process to pick some number n of drugs. Each player plays in turn by adding one, two, or three edges. The first player whose edge(s) does(do) not increase the number of maximal cocktails loses. Is there a winning strategy for this game?
Upstart 2: From a practical point of view for drugs, we might want to try maximal cocktails that are quite different from one another. Call two sets of drugs D1 and D2 k-similar if they have at least k drugs in common. Play the same game as in Upstart 1 where we want to avoid maximal cocktails that are 2-similar or more. How about for arbitrary k?
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2023 ACM, Inc.
No entries found