The block-interchange distance problem is defined as finding the minimal number of subsequences swaps to apply to an input string to turn it into a desired string. It is a well studied tractable problem in the context of permutations due to its applications in genetics. However, I was unable to find any complexity results for it in a setting where the alphabet is fixed, especially binary strings. A variant of it is the interchange problem where elements are swapped, and it's tractable for binary strings. What complexity results are there for the block-interchange distance problem over binary strings in terms of tractability and approximation?

  • 1
    $\begingroup$ Regarding tractability: if it is tractable for variable alphabet, it should be tractable also for binary strings (fixed alphabet). $\endgroup$ Feb 7 at 13:16
  • $\begingroup$ @MarzioDeBiasi The main assumption that made the problem tractable in the case of permutations is that the strings contain distinct elements since they contain all integers from 1 to n where n is allowed to increase. It seems to me that the problem is harder when elements are not distinct. $\endgroup$ Feb 7 at 15:38
  • 1
    $\begingroup$ Ok. Perhaps you could add the (formal) definition of the problem in your question? (the linked paper is beyond paywall, so a definition could help to make the question self-contained). And also clarify why you use "minimize the number of subsequences swaps" (while the paper talks about "the minimum weight of block-interchanges" (didn't read it carefully, so perhaps they have the same meaning) $\endgroup$ Feb 8 at 12:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.