Question: What is the connection between the directed graph tightness problem (described in the paper) and SBT? Specifically, (i) if directed graph tightness is NP-Hard, does it imply that SBT is NP-Hard? (ii) if directed graph tightness is polynomial, does it imply that SBT is polynomial?

Answer: The short answer to both questions is: almost, but not quite.

Specifically, An NPC proof for directed graph tightness would not directly imply that SBT is NPC. Proving that SBT is NPC would require showing a set of directed graphs for which checking tightness is hard, such that all of these graphs can indeed arise from instances of SBT. Not all graphs can arise from instances of SBT: This is similar to the situation in SBR, where the interleaving graphs that Hannenhalli and Pevzner get from permutations are necessarily circle graphs, so non-circle graphs cannot arise from instances of SBR. I personally believe that if directed graph tightness is NPC then all that separates us from a proof that SBT is NPC are technical details, maybe some ugly case-analysis or something of the sort, that shows that the construction of the NP-Hard instances can indeed come from a valid input to SBT. However, I don't know how to prove this, and the most reasonable approach seems to first prove that directed graph tightness is hard, and then try to find a set of hard instances which arise from SBT.

About the other direction, that is if a poly-time algorithm for directed graph tightness implies a poly-time algorithm for SBT, the situation is more involved. First, you want to take the hypothetical poly-time algorithm and generalize it to check tightness of Hermitian matrices over the ring M which we define in the paper. This is hopefully the easy part, and there's good chances that all arguments will go through since Hermitian matrices over M are a not-too-major generalization of (non-symmetric) matrices over F_2. Now, if you have a poly-time algorithm for checking tightness of Hermitian matrices over the ring M, then you already solved a nice open question, because this immediately gives a poly-time algorithm that checks for simple permutations whether their transposition distance is n/3. However, you still have some way to go to get a poly-time algorithm for SBT: You can sort all tight permutations, but you can't do anything for non-tight permutations. You need to do something analogous to what Pevzner and Hanenhalli did with "hurdles" -- that is, you need to find a way to compute the transposition distance of non-tight permutations by identifying the "hurdles" in SBT. And then you'd be done.

Specifically, it would be better for that purpose if you not only find a poly-time algorithm that recognizes tight directed graphs, but you would want to find a _characterization_ of tight directed graphs, much like Hannenhalli and Pevzner found a characterization of tight undirected graphs (a graph is tight iff there is a black vertex in each connected component). Because then you'd have some lead how to look for hurdles.

And if anyone has ideas, I'd love to hear them. Directed graph tightness currently seems to me to be a good way to approach SBT.