Grouping By Swapping

Here is the actual problem in G&J that will use the Non-Minimal Feedback Arc Set problem from last week:

The problem: Grouping By Swapping.  This is problem SR21 in the appendix.

The description: Given a string x over some finite alphabet, and an integer K, can we convert x into a string that groups all characters together in adjacent positions by using K or less swaps of adjacent symbols?

Example: Suppose x was abcabccba

Our goal is to create a string where all of the a’s are consecutive, all of the b’s are consecutive, and all of the c’s are consecutive. So for example, we could try to gather the b’s together in the middle.

• Start with abcabccba
• 2 swaps get us acabbccba
• 2 swaps get is acabbbcca
• Now we need to bring the c’s together.  4 swaps get is aabbbccca
• Now we need to bring the a’s together.  Swapping from the right we can get aaabbbccc in 6 more swaps.  This is a total of 14 swaps

A better method would be to try to bring the c’s together first:

• Start with abcabccba
• 2 swaps get us ababcccba
• 3 swaps get us to ababbccca
• 1 swap gets us to aabbbccca
• 6 swaps get us to aaabbbccc.  This is a total of 12 swaps.

Note that there is no rule that the a’s have to come before the b’s or anything.  If we could get a final string of, say, bbbaaaccc in less total swaps, that would be fine.

Reduction:   I should start by noting how similar this problem is to String-To-String Correction, especially since that problem is also NP-Complete in the case where the only operation allowed is swapping (instead of swapping or deleting).  I was hoping to find a good simple reduction between these two problems.  But I couldn’t figure out a way to relate the fact that String-To-String correction gives you a destination string to use, but Grouping By Swapping allows you to come up with any string, as long as the characters are grouped together.  Doing all possible permutations of the alphabet as possible destination strings in a kind of Turing Reduction is too many possibilities, and I couldn’t think of a way to change x to force the best solution to this problem to relate to the needed y in the String-To-String Correction problem.

So, instead, we’ll use the paper by Paterson and Razborov that we used last week for the Non-Minimal Feedback Arc Set reduction which reduces from that problem here.   They actually show a stronger problem- given a string x, can we find a permutation of the alphabet that has less inversions (out of order characters) on x than there is now?

(Since an inversion is “fixed” by swapping two characters to put them in order, we can reduce from this problem to our grouping by swapping problem by setting K to be the number of inversions in x)

We’re given an instance of Non-Minimal Feedback Arc Set- A directed graph G=(V,A) and a set S of edges that forms a feedback arc set in G.  Give each vertex a number so that if we have an edge (v_i, v_j) in A-S, then i < j .

The string that will be built is based on a palindrome.  Palindromes have the property that no matter what permutation of the alphabet, there is always the same number of inversions.  (The way this relates to the original grouping by swapping problem is that all permutations of the characters in the final grouped string will have the same number of swaps).  Note that if we swap 2 characters in a palindrome in the “wrong way” (away from where they will eventually end up)  we will add 2 to the number of inversions.

Suppose |A| was p, and edge a_j was (u,v).  Define e_j to be “uv” and E_j to be “vu”.  The string w = e₁e₂..e_pe_p..e₂e₁ is not quite a palindrome because we’re using “uv” in both the first half and the second half.  The palindrome we want is: e₁e₂..e_pE_p..E₂E_1.

That palindrome has the same number of swaps to get to any legal grouping of characters.  Call that number of swaps q.    Given a permutation π of the alphabet, we can use the ordering of the vertices to find out how many edges in the graph are out of order in this permutation.  Call this number back(π).

So the total number of inversions of w given a permutation π is q-|A|+2*back(π). (The inversions of the palindrome, minus all of the edges in A that were e instead of E, plus the penalty of 2 for each edge that is “wrong” in the inversion we’re using)

So, the original graph has feedback arc set smaller than S if and only if we can find a permutation π where back(π) < |S|.  This happens if and only if we can find a permutation with less inversions than the identity permutation (the one that we got from the ordering of the vertices based on S), which only happens if w is a solution to the modified Grouping by Swapping problem.

Difficulty: 9.  I’ll be honest, I don’t really but the end of the reduction.  I don’t really see how they’re using the feedback set S anywhere except for the initial ordering.  So I’m not following those last couple of “if and only if” steps  Maybe I’m missing something.

I do like the idea that a palindrome has the same number of inversions, no matter what your final order is.  I wish I could think of a way to use that in a reduction from String-To-String Correction that was easier.