<p>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 <a href="https://www.sciencedirect.com/science/article/abs/pii/S002001909600155X" rel="nofollow noreferrer">permutations</a> 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 <a href="https://link.springer.com/chapter/10.1007/978-3-540-75520-3_11" rel="nofollow noreferrer">binary strings</a>. What complexity results are there for the block-interchange distance problem over binary strings in terms of tractability and approximation?</p>

CC BY-SA 4.0
2024-02-07T13:16:19.833Z
Regarding tractability: if it is tractable for variable alphabet, it should be tractable also for binary strings (fixed alphabet).
Marzio De Biasi
CC BY-SA 4.0
2024-02-07T15:38:07.417Z
@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.
Daniel García
CC BY-SA 4.0
2024-02-08T12:15:19.527Z
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)
Marzio De Biasi
<cc.complexity-theory><reference-request><np-hardness>
On The Complexity of Block-Interchange Distance for Binary Strings
Daniel García
# On The Complexity of Block-Interchange Distance for Binary Strings

(Asked by: username_0 on 2024-02-07)

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](https://www.sciencedirect.com/science/article/abs/pii/S002001909600155X) 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](https://link.springer.com/chapter/10.1007/978-3-540-75520-3_11). What complexity results are there for the block-interchange distance problem over binary strings in terms of tractability and approximation?

**Tags:** cc.complexity-theory, reference-request, np-hardness

> **Comments:**
> **username_1**: Regarding tractability: if it is tractable for variable alphabet, it should be tractable also for binary strings (fixed alphabet).  
> **username_0**: @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.  
> **username_1**: 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)  

---

## 0 answers

