# Is there a solution for this maze problem in polynomial time?

Suppose you have a maze represented by a graph where each vertex represents a room and edges represent paths between rooms and each edge has a weight denoting the time it takes to go that way. Now here comes the tricky part: suppose each room needs a set of keys for you to enter, and inside each room you can find another set of keys. Keys can be repeated and one key may be needed to enter on more than one room. You can only enter the room if you have all keys required.

You have an arbitrarily large number of chests with gold inside and each chest needs one key which can be found in the maze. You already have a set of keys that you can use. You can use a key more than once. The question is: how do you collect the keys you need as fast as possible?

• – D.W. Aug 28 '18 at 22:52
• Are you looking for practical solutions or for the theoretical complexity? If practical solutions: about how many keys are there, total? About how many keys per room/door? About how many rooms? Since you ask about polynomial time, polynomial in what? Is the number of keys a constant or can it be arbitrarily large? – D.W. Aug 28 '18 at 22:54
• What have you tried? Have you tried to prove it NP-hard by finding a suitable reduction? What problems have you tried to reduce from? – D.W. Aug 28 '18 at 22:55
• I couldn't come up with a reduction. I thought about reducing to TSP, but couldn't. the best solution I thought of was the one described by @orlp's answer, which would be $O(2^(number of keys) * number of halls)$ – Caio Oliveira Aug 29 '18 at 17:59
• Also, the amount of chests you want to open is arbitrary. I'll update the question to account for that – Caio Oliveira Aug 29 '18 at 18:00

If the number of keys is unlimited, the problem is NP-hard, by a straightforward reduction from the traveling salesman problem: simply put a different key in each vertex, and have a single chest that requires all the keys.

If the number of keys is a constant, there is a polynomial time solution, simple shortest path graph algorithm.

The trick is to duplicate the maze $2^k$ times, where $k$ is the number of keys - once for each possible subset of keys. Then in each copy of the maze remove all the edges for which you do not have the sufficient keys in that copy.

Finally, for each place that gives you a key make an edge between the two duplicated places, from the graph without the key to the one with the key.

• the number of keys is arbitrary – Caio Oliveira Aug 29 '18 at 18:00