The next problem in the Appendix is “Register Sufficiency for Loops”, which basically asks “Given a set of loop variables and K registers, can we assign variables to registers so that there is no conflict between loop iterations?”. The reduction is better explained in two parts. This is the first part.

**The problem: **The “Word Problem for Products of Symmetric Groups” (WPPSG). This is not in the appendix. It is defined in the paper by Garey, Johnson, Miller, and Papadimitriou that has the reduction we will want for the Register Sufficiency for Loops problem.

**The description: **Given an integer K, and m sets X_{1} through X_{m}, each containing a subset of {1..K}, and a permutation π of the numbers from 1-K. Can we get π by a series of permutations defined by permuting with X_{1}, then X_{2}, and so on through X_{k}?

**Example:**

To “permute with” an X_{i} set, I mean we can rearrange the elements corresponding to the positions in X_{i} however we want, but elements that are not listed in X_{i} do not move.

So, suppose we had K=5 and 3 sets:

X_{1} = {1,3,5}

X_{2} = {2,3}

X_{3} = {4,5}

If π = {3,1,2,5,4}, we can do this by first permuting with X_{1 }using {3.1,5} turning {1,2,3,4,5} into {3,2,1,4,5}. Then we permute X_{2} using {3,2},turning {3,2,1,4,5} into {3,1,2,4,5}. Finally, we permute X_{3}, using {5,4} turning {3,2,1,4,5} into {3,2,1,5,4}.

If π = {2,1,5,3,4} we can’t do it. There is no way to get a 2 into the first location, since the only permutation that can possibly place something in the first location is X_{1}, and we have to do the X permutations in order.

**Reduction:**

If you’re following along, this is Theorem 2 of the paper. They go from Disjoint Connecting Paths, but add the restriction that the graphs are directed acyclic graphs. (They say it’s a “trivial modification” to a standard reduction. We did that reduction slightly differently, but since we went from a flow problem, I think it is fine to convert that to do a DAG version of the problem reduction from a directed version of the flow problem).

They also modify the problem so that the start vertices all have indegree 0 (and all vertices with indegree 0 are start vertices), and all end vertices have outdegree 0 (and all vertices with outdegree 0 are end vertices).

So, we’re given a DAG G, and a set of start vertices s_{1}..s_{n} along with their matching end vertices t_{1}..t_{n}. First, we will take the graph and replace all edges a= (u,v) with a pair of edges going through a new vertex just for edge a: (u, w_{a}) and (w_{a}, v). That new vertex is “private” to the edge and is not used anywhere else. Our new graph G’ has q vertices.

Since we do have a DAG, we can topologically sort the vertices. Set up a sorting so that the first vertices in the sort are the vertices s_{1}..s_{n}. We can get away with this because all of the s vertices have indegree 0. Similarly, make the last vertices in the sorting be t_{1}..t_{n}.

For each vertex v_{i}, define B(i) = {j:(v_{i}, v_{j}) is an edge}.

Now we’re ready to build our WPPSG instance. Our X sets are:

X_{j} = {n+j} ∪ B(n+j) for j from 1 to q-n

The last set is X_{q-n+1} = {1,2,…q-n}

The permutation we want to build is:

π(i) = q-n+i for i from 1 to n

π(i) = i-n for i from n+1 to q.

Our WPPSG instance has one position in its permutation for each vertex in G’. Every position starts labeled by its own index. Each set X_{i} contains vertex v_{n+1} and its immediate predecessors. So permutation X_{1} will replace s_{1} with a label of one of its neighbors, which corresponds to moving along that edge. Suppose we permute s_{1} with some vertex v. Then when we get to X_{v}, we will permute with one of v’s neighbors, and so on down the chain until we get the final position on a t vertex. The final permutation ensures that we have eventually permuted the labels to end up with their corresponding t vertices. (It doesn’t matter what happens with the rest of the labels).

**Difficulty: **7. I like the idea of “pushing” a path through a graph into a permutation problem.