5
\$\begingroup\$

This is a joint post with https://puzzling.stackexchange.com/questions/126255/dishonest-dungeon-staff

You are faced with the difficult task to set up a dungeon for adventurers. However you made a deal with the guild: any adventurer brave enough to beat the dungeon and reach the treasure room will be guaranteed to receive some treasure, whatever he or she does. Of course, this goes against your master's rules, and so you will need to be clever about it. Under normal circumstances, the treasure room works as follows:

There are N keys, and M rooms containing one treasure chest each. Every key opens at least one chest, and every chest has at least one key opening it, but you have no control over which keys open which chests. Each adventurer can pick a key, enter one chest room, and attempt to open each chest reachable from that room, with each key in his or her possession. Your plan is to place the keys on keyrings (so that an adventurer that picks a key also gets any other keys on the same keyring), and dig tunnels connecting different chest rooms (so that an adventurer that enters a chest room can also reach any other rooms connected to it via tunnels), so that for every combination of keyring and chest room, there is at least one key on the keyring that can open a chest reachable from that room. Now, if you were unsupervised, you could put all N keys on the same keyring and connect all M rooms to each other, but you are under close surveillance, so you will need to minimize the risk of getting caught. In practice, this means that you will need to ensure the adventurer wins, with the fewest combinations of keys and chest. For example, combining key 1 and key 2 in one key ring and then combining this key ring with key 3 counts for 2 combinations, and the same goes for chests. You don't have all eternity to find a solution. Your procedure should be able to tell you the actions to take in a reasonable time as a function of N and M.

Is there a way you can ensure you fulfill your contract in the minimum number of combinations?

Input :

  • N,M two integers with no dominance
  • For each chest the list of keys that opens it.

Output : The minimum number of combinations that satisfies the constraint.

No testing set is provided. However I will provide one example:

  • N=M=4: Chest 1 is opened by key 4, chest 2 by key 2 and key 3, chest 3 by key 1, key 2 and key 4, and chest 4 by the same keys as chest 3. The minimum number of moves is 2 : dig a tunnel between the chest 1 and 2, combine key 1 and 3. After this, you can check any key group you take can open at least on chest in each chest group.

Answer should provide an algorithm alongside a proof of it's correctness and an arbitrarily detailed complexity analysis, or a proof that this problem is not solvable in polynomial time, i.e. a proof of NP-completeness. Fastest algorithm wins, or first to prove it is NP-complete. Here we are looking at the worst case complexity w.r.t. the size of the input N*M.

Good luck!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ If the input is just two integers N,M and the output is just the minimum number of combinations, where does the information of "Chest 1 is opened by key 4, chest 2 by key 2 and key 3, chest 3 by key 1, key 2 and key 4, and chest 4 by the same keys as chest 3." come from in your example? Or is what chest is opened by what key also up to ourselves when determining the algorithm for the minimum amount of combinations? \$\endgroup\$ Commented Apr 22 at 12:55
  • 2
    \$\begingroup\$ Good remark I totally forgot to put that in. I wish someone made it when it was still in the sandbox :/ \$\endgroup\$
    – Fluorine
    Commented Apr 22 at 12:59

1 Answer 1

3
\$\begingroup\$

Partial answer towards NP-hardness

The problem is equivalent to the following:

A bipartite graph \$G = (U, V, E)\$ is given, where \$U\$ and \$V\$ are sets of disjoint vertices and \$E\$ is the set of edges. Let \$|U| = n\$ and \$|V| = m\$. Maximize \$a + b\$ where it is possible to transform \$G\$ to a complete bipartite graph \$K_{a,b}\$ by merging some vertices within the same set. If two vertices \$x\$ and \$y\$ are merged, all incident edges \$(x, x')\$ and \$(y, y')\$ transform into \$(\{x, y\}, x')\$ and \$(\{x, y\}, y')\$.

When the maximum value of \$a+b\$ is known, the answer to the original problem is \$n + m - (a + b)\$.

We can think of two decision problem versions of this problem:

\$(a+b)\$-Complete Bipartite Reduction: Decide if \$G\$ can be transformed into \$K_{a,b}\$ for some pair \$(a, b)\$ where the value of \$a+b\$ is given.

\$(a+b)\$-CBR and the original problem can be reduced to each other in polynomial time.

\$(a, b)\$-Complete Bipartite Reduction: Decide if \$G\$ can be transformed into \$K_{a,b}\$.

If we can solve \$(a,b)\$-CBR in polynomial time, we can solve \$(a+b)\$-CBR in polynomial time. I conjecture that the converse is also true, but there might be a very clever polynomial-time algorithm that only solves for \$(a+b)\$ but not for any specific \$(a,b)\$.

Claim: \$(a,b)\$-CBR is NP-hard.

Proof: Reduction from \$k\$-Disjoint Set Cover [1].

\$k\$-DSC: given a collection \$C\$ of subsets of a finite set \$T\$, decide if \$k\$ disjoint covers for \$T\$ can be made from \$C\$.

Let \$U = C\$ and \$V = T\$, and add an edge between \$C_i\$ and \$T_j\$ when \$T_j \in C_i\$. Now consider \$(k, |T|)\$-CBR on this graph. Each left node in the transformed complete bipartite graph represents a cover for \$T\$. \$k\$ left nodes represent \$k\$ disjoint sets of sets in \$C\$. Therefore the answer to \$(k, |T|)\$-CBR is the answer to \$k\$-DSC, and if the former is solved in polynomial time, so is the latter.

[1] Improving Wireless Sensor Network Lifetime through Power Aware Organization

\$\endgroup\$
3
  • \$\begingroup\$ What you provided is an interesting starting point. One small remark, the notation (a+b)-CBR is confusing, since a and b are not parameters in that instance. I would suggest replacing it by k-CBR, and the question would be to decide if there exists K_a,b with k=a+b such that G can be reduced to K_a,b. Also can you clarify whether G is already bipartite in all the problems? For the rest I find your proof convincing, and I commend your research effort \$\endgroup\$
    – Fluorine
    Commented Apr 24 at 13:42
  • 1
    \$\begingroup\$ This is where my brain went exactly, and the reduction from k-disjoint set cover is clever. I would note that the original problem also gives the assumption that "Every key opens at least one chest, and every chest has at least one key opening it" which translates to G having a minimum degree of 1. In practice this makes no difference since it can be quite easily reduced to and from the same problem on any bipartite G, but I though it was worth mentioning. \$\endgroup\$ Commented Apr 25 at 18:25
  • \$\begingroup\$ I'm pretty sure you can use a polynomial-time oracle for (a+b)-CBR to solve k-DSC. Let U=C and V=T x Z_|C| where there is an edge between C_i and (T_j, _) if T_j is in C_i. The max solution for (a+b)-CBR should have a+b = |C|*|T| + k. If there is a (k,|T|)-CBR for the original graph, then choosing the same left nodes leads to a (k,|C|*|T|)-CBR for the new graph. Otherwise for any choice of k left nodes in the original graph, there is at least one node with q<=|T|-1 edges, corresponding to at most a (k,|C|*|T|-|C|)-CBR. Since k<=|C| and there exists a (1,|C|*|T|)-CBR, that can't be the maximum. \$\endgroup\$
    – gsitcia
    Commented Apr 29 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.