Uniformly randomly generating an "unlockable" graph

Question

I'm working with something that can modeled as the following type of (multi-)graph $G = (V,E)$, which I've been calling an "unlockable" graph. (There may be existing terminology for this.)

Let $G$ be a graph with the following additional structure. There is a set $K$ of keys, and edges may be "unlocked" or they may be "locked" by decorating them with the name of some $k \in K$. Multiple edges can be locked by the same $k$. Each vertex in the graph $v_i$ has a (possibly empty) ordered list $L_i$ of locations, which may be empty or contain a key. One of the vertices of the graph is marked as the start vertex.

The graph can be completely unlocked if every vertex can be visited from the start vertex. A locked edge can only be traversed if a vertex containing the key for that edge is first visited. Traversals are allowed to repeat edges and vertices.

Such a graph is valid if a) all keys are placed in exactly one location and b) the graph can be completely unlocked.

I'd like to uniformly randomly select a valid key placement on a fixed underlying graph. (That is, a map from $K$ into the locations $L = \cup_i L_i$ of the graph.)

---

The analogy (and essentially the context) is as follows: The graph represents a dungeon composed of rooms, and the edges are doors, which can be locked or unlocked by various keys. These keys are scattered around the dungeon in treasure chests. An adventurer enters the dungeon and explores it, and wins if they can enter every single room (to loot it, I suppose). How can the keys be distributed so that the adventurer always wins, and cannot have an unfair advantage by assuming that one valid configuration is more likely than others?

---

Here's a naive algorithm that produces a random valid key placement:

current_keys = {}
placed_keys = {}
current_rooms = {}
while not all rooms are in current_rooms:
    current_rooms = largest connected component of start_room via unlocked doors
    for key not in current_keys and key not in placed_keys:
        if key has door connected to room in current_rooms:
            add key to current_keys
    randomly select new_key in current_keys
    place new_key in random unused location in room in current_rooms
    remove new_key from current_keys
    add new_key to placed_keys
    unlock all doors that can be opened using new_key

However, this algorithm does not randomly select a valid key placement uniformly.

For instance, imagine a dungeon consisting of three rooms: a start room and two side rooms connected to it. The door to one side room needs key $a$ and the door to the other needs key $b$. Each side room has one chest, and the starting room has two. I'll draw this dungeon as [_|__|_], with the start room in the middle, the $a$ side room on the left, and the $b$ side room on the right.

There are six distinct valid configurations:

[_|ab|_], [_|ba|_], [b|a_|_], [b|_a|_], [_|b_|a], [_|_b|a]

However, the naive algorithm over-weights the first two choices, selecting them 1/4 of the time each and the remaining choices only 1/8 of the time. This is because earlier areas are unlocked for longer, so they have a higher chance to have a key placed in them.

Also notice that [_|ab|_] and [_|ba|_] are distinct configurations, since the elements of $L_i$ are distinguishable from each other. It is not the same as specifying that $v_i$ can hold at most $|L_i|$ keys.

I thought about something like a dynamic programming-type algorithm, but the issue is that a valid configuration can be produced from an invalid configuration. For example, if we always placed $a$ before $b$ in the above example, then the configurations [_|b_|a] and [_|_b|a] could never be reached because [_|__|a] is not a valid partial configuration.

---

It's pretty clear that there are roughly at most $|L|^{|K|}$-many key placements, although for a generic graph, a good portion of these will not be valid.

In my particular problem, I have about 40 rooms with about 100 treasure chests spread around among them and about 20 keys. Enumerating all possible valid locations and then uniformly choosing a random one seems like it would be quite slow, especially if I want to use this for a larger scenario, where I have about 50 rooms with 1000 chests and 40 keys.

This question is pretty specific and I couldn't find any information about this type of graph, but I also don't really know what to search for it as.

I did find some information about generating such graphs where you can also choose which doors are unlocked with which keys -- in the context of surprise, surprise, dungeon generation for a game -- but here that information is fixed in advance and only the keys can be freely placed.

(I'm also interested in a harder problem where some of the doors are one-way (so the graph is a digraph) and we don't want the adventurer to ever get stuck in a room with no way out, but I suspect the above problem is hard enough to start.)

Answer 1

The following decision variant of your problem is NP-hard in general:

Given a graph,determine whether the graph has any valid placement of keys to make it unlockable.

In particular, there's a straightforward reduction from 3SAT, shown below in the appendix.

As a consequence, in the general case your problem is NP-hard too: take the graph, try to sample a valid placement of keys, and if the procedure returns a valid placement, then you know the graph is unlockable; if it gives up, the graph is not unlockable. However, this might not be terribly relevant in practice.

It does suggest a possible approach to your problem. We could construct a formula $\psi$ where every satisfying assignment corresponds to a valid placement of keys that makes the graph unlockable, and then ask to randomly sample from the satisfying assignments of $\psi$. It should be straightforward to construct such a formula; then see Using SMT solvers to generate random solutions to given predicate for one method for doing the latter. This approach will be exponential-time in the worst case, but it's possible that if your problem has enough structure, maybe it will be effective in practice.

---

Appendix: The reduction

Suppose we have a 3CNF formula $\phi$ with $n$ variables $x_1,\dots,x_n$ and $m$ clauses. We'll have $2n$ keys (one for each $x_i$ and one for its negation, $\neg x_i$). The graph is a sequence of $n$ diamonds, one for each variable, followed by a sequence of $m$ vertices, one for each clause, like this:

I haven't shown the edge decorations or locations yet. Let's start with the $i$th diamond (corresponding to the $i$th variable, $x_i$):

The edge $A_i \to B_i$ is decorated with the key $x_i$, and the edge $A_i \to C_i$ is decorated with the key $\neg x_i$. There is one location associated with $A_i$; $B_i$ and $C_i$ have no locations. Notice how this forces any valid placement to put either $x_i$ or $\neg x_i$ into the location at $A_i$, and in particular, we can either place the key $x_i$ somewhere or place the key $\neg x_i$ somewhere.

Next, let's look at one of the pieces of the right half of the graph, corresponding to the $j$th clause.:

I've shown the decorations we'd get if the clause is $(x_3 \lor \neg x_5 \lor \neg x_7)$.

Finally, we add $n$ more isolated vertices $D_1,\dots,D_n$ (not shown above), each with a single location. The idea is that the keys that aren't placed into $A_1,\dots,A_n$ will be placed in $D_1,\dots,D_n$, so each key can be placed in exactly one location.

Note that $V_m$ will be reachable if and only if there exists an assignment that satisfies the formula $x_i$.

Answer 2

One approach is to use rejection sampling. In other words:

1. Randomly sample a placement of keys in locations (without regard to whether that placement allows the graph to be completely unlocked).

2. Test whether the resulting graph can be completely unlocked. If not, repeat (go back to step 1, and keep repeating until you find one that can be unlocked).

This does have a uniform random distribution on the set of valid graphs. The running time depends on what fraction of random placements allow the graph to be completely unlocked; I don't know what that fraction is.

There may be better algorithms.