Tag Archives: Not in Appendix

Word Problem For Products of Symmetric Groups

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 X1 through Xm, 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 X1, then X2, and so on through Xk?

Example:

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

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

X1 = {1,3,5}

X2 = {2,3}

X3 = {4,5}

If π = {3,1,2,5,4}, we can do this by first permuting with Xusing {3.1,5} turning {1,2,3,4,5} into {3,2,1,4,5}.  Then we permute X2 using {3,2},turning {3,2,1,4,5} into {3,1,2,4,5}.  Finally, we permute X3, 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 X1, 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 s1..sn along with their matching end vertices t1..tn.  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, wa) and (wa, 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 s1..sn. We can get away with this because all of the s vertices have indegree 0. Similarly, make the last vertices in the sorting be t1..tn.

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

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

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

The last set is Xq-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 Xi contains vertex vn+1 and its immediate predecessors.  So permutation X1 will replace s1 with a label of one of its neighbors, which corresponds to moving along that edge.  Suppose we permute s1 with some vertex v.  Then when we get to Xv, 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.

Protected: Regular Expression Inequivalence on Single Character Alphabets

This content is password protected. To view it please enter your password below:

Protected: Linear Space Acceptance

This content is password protected. To view it please enter your password below:

Protected: Maximum Leaf Spanning Tree, Connected Dominating Set

This content is password protected. To view it please enter your password below:

Protected: Hamiltonian Path on Bipartite Graphs

This content is password protected. To view it please enter your password below: