\( \newcommand\norm[1]{\lvert\lvert#1\rvert\rvert} \newcommand\epi{\bar{\pi}} \newcommand\eiota{\bar{\iota}} \newcommand\spi{{\eiota}{\epi}^{-1}} \)

SBT 1.375

This document contains proofs for results presented on the paper "A new 1.375-approximation algorithm for Sorting By Transpositions" by L. A. G. Silva, L. A. B. Kowada, N. R. Rocco and M. E. M. T. Walter.

Download

The whole document containing all generated HTML files can be downloaded using this link.

Structure

The structure of the proofs of lemmas 1, 2 and 3 is explained here.

Main results

Lemma 31: If it is possible to build a sufficient configuration $\Gamma$ of $\spi$ such that $\Gamma$ is big, then $\Gamma$ allows an $\frac{11}{8}$-sequence.

Lemma 32: The bad small components are:

  1. the bad oriented $5$-cycle
  2. the unoriented interleaving pair
  3. the unoriented necklace of size $4$
  4. the twisted necklace of size $4$
  5. the unoriented necklace of size $5$
  6. the unoriented necklace of size $6$
The demonstration of the previous results employs a case analysis performed using a Depth First Search (DFS), in which, the configurations, starting from the ones listed below, are systematically extended until $\frac{11}{8}$-sequences are found:
  1. the bad oriented $5$-cycle
  2. the unoriented interleaving pair
  3. the unoriented intersecting pair
No configuration with $3$-norm equals to $10$ was reached during the search. The search found the full configuration (0 9 2)(1 11 4)(3 8 6)(5 10 7) which does not allow a $\frac{11}{8}$-sequence. However, note that this configuration is invalid, since in this case, $\spi\epi=\eiota=(0\;5\;2)(1\;10\;3)(4\;9\;7)(6\;11\;8)(0\;1\;2\;3\;4\;5\;6\;7\;8\;9\;10\;11)=(0\;10\;8\;7\;6\;4\;2\;1)(3\;9)(5\;11)$, and thus $\eiota$ is not a $(n+1)$-cycle (see Proposition 40 in this page).

Lemma 33: If there is a configuration $\Lambda$ of $\spi$ consisting only of bad small components such that $\norm{\Lambda}_3 \geq 8$, then $\Lambda$ allows a $\frac{11}{8}$-sequence.

In order to demonstrate this result, we also employ an approach similar to a DFS search, in which, starting from the bad small component listed above, we extend the configurations by adding another bad small component in a different position of $\epi$, until $\frac{11}{8}$-sequences are found. We note that by this approach no combination of bad small components with $3$-norm greater than 7 was extended. Below, the result of the search:
  1. the bad oriented $5$-cycle
  2. the unoriented interleaving pair
  3. the unoriented necklace of size $4$
  4. the twisted necklace of size $4$
  5. the unoriented necklace of size $5$
  6. the unoriented necklace of size $6$

Auxiliary results

Proposition 16: The permutation $\spi$ is an even permutation.

Proposition 25: If there is an oriented $3$-cycle $\gamma=(a\;b\;c)$ in $\spi$, then a $2$-move exists.

Proof. In this case, $(a\;b\;c)$ is a $2$-move.

Proposition 26: If there is an odd (even-length) cycle in $\spi$, then a $2$-move exists.

Proof. Since $\spi$ is an even permutation (Proposition 14), then there is an even number of odd cycles in $\spi$. Let $\gamma=(a\;b\dots)$ and $\delta=(c\;d\dots)$ be two odd cycles of $\spi$. We have two cases:
(1) $\gamma$ and $\delta$ intersect. In this case, we have that $\epi^{-1}=(a\dots d\dots b\dots c\dots)$. Then $(a\;b\;c)$ is a $2$-move.
(2) $\gamma$ and $\delta$ do not intersect. W.l.o.g, suppose $\epi^{-1}=(a\dots b\dots c\dots d\dots)$. In this case, $(a\;c\;b)$ is a $2$-move. Note that $\epi^{-1}=(a\dots c\dots d\dots b\dots)$ is not a distinct case, being equivalent to a cyclic rotation of $(a\dots b\dots c\dots d\dots)$ with the symbols $a$ and $b$ chosen differently.

Lemma 27: If there is a $5$-cycle $\gamma=(a\;d\;b\;e\;c)$ in $\spi$ such that $(a,b,c)$ is an oriented triplet, then there is a $2$-move or a $(3,2)$-sequence.

Proof. The possible forms of $\epi$ relatively to the positions of the symbols of $Supp(\gamma)$ are listed below. For each one, there is either a $2$-move or a $(3,2)$-sequence.
(1) $\epi=(a\dots b\dots c\dots d\dots e\dots)$. $\tau_1=(a\;b\;c)$, $\tau_2=(b\;c\;d)$, $\tau_3=(c\;d\;e)$.
(2) $\epi=(a\dots b\dots c\dots e\dots d\dots)$. $\tau_1=(b\;e\;d)$.
(3) $\epi=(a\dots b\dots e\dots c\dots d\dots)$. $\tau_1=(a\;e\;c)$.
(4) $\epi=(a\dots e\dots b\dots d\dots c\dots)$. $\tau_1=(a\;d\;c)$.
(5) $\epi=(a\dots b\dots e\dots d\dots c\dots)$. $\tau_1=(a\;d\;c)$.
(6) $\epi=(a\dots d\dots b\dots e\dots c\dots)$. $\tau_1=(a\;d\;b)$.

Lemma 28: If there is an even (odd-length) $\kappa$-cycle $\gamma=(a\dots b\dots c\dots)$ in $\spi$ such that $\kappa\geq 7$ and $(a,b,c)$ is an oriented triplet, then there is either a $2$-move or $(4,3)$-sequence.

Proof. If $(a\;b\;c)$ is a $2$-move, then the lemma holds. There is only one case where $(a\;b\;c)$ would not be a $2$-move. W.l.o.g, suppose that this case is \[ \gamma=(\underbrace{d\;e\dots b}_{odd}\;|\;\underbrace{f\dots c}_{even}\;|\;\underbrace{g\dots a}_{even}\;|). \] Vertical bars are used to indicate the locations where $\gamma$ would be broken if $(a\;b\;c)$ were applied on $\epi$, and subscripts to indicate the parity of the length of the resulting cycles. Note that the cycle $\gamma$ can be rewritten as the product \[ \gamma=(\underbrace{a\dots}_{odd})(\underbrace{b\dots}_{odd})(\underbrace{c\dots}_{odd})(a\;d\;e\;b\;f\;c\;g). \] There is only one form of $\epi$ relatively to the symbols of the support of $(a\;d\;e\;b\;f\;c\;g)$ not allowing the application of a $2$-move. It is $\epi=(a\dots e\dots f\dots g\dots d\dots b\dots$ $ c\dots)$. For this $\epi$, $\tau_1=(a\;e\;f)$, $\tau_2=(d\;e\;f)$, $\tau_3=(b\;f\;d)$, $\tau_4=(a\;c\;g)$ is $(4,3)$-sequence of transpositions.

Lemma 29: If $\spi\neq\iota$, then a $2$-move or $(3,2)$-sequence exists.

Proof. If there is an odd (even-length) cycle in $\spi$, then by Proposition 24, a $2$-move (i.e., a $(1,1)$-sequence) exists. Thus, we assume $\spi$ containing only even (odd-length) cycles.

(1) There is an oriented $\kappa$-cycle $\gamma$ in $\spi$. If $\kappa=3$, then Proposition 23 gives a $2$-move and the lemma holds. If $\kappa=5$, then Lemma 25 gives a $2$-move or $\gamma$ is the bad oriented $5$-cycle. In this case, there is a $(3,2)$-sequence. On the other hand, if $\kappa \geq 7$, then a $2$-move or a $(4,3)$-sequence, which contains a $(3,2)$-sequence, is given by Lemma 26.
(2) All the cycles of $\spi$ are unoriented. Let $\gamma=(a\;b\;c)$ be a segment of a cycle of $\spi$. We have two subcases:
  (2.a) $\gamma$ interleaves with another segment $\delta=(d\;e\;f)$. In this case, $\epi=(a\dots f\dots c\dots e\dots b\dots d\dots )$. Then, $\tau_1=(a\;c\;b)$, $\tau_2=(d\;e\;f)$ and $\tau_3=(a\;c\;b)$ is a $(3,2)$-sequence.
  (2.b) $\gamma$ intersects with two segments $\delta=(d\;e\;f)$ and $\epsilon=(g\;h\;i)$. For each of the $15$ distinct forms of $\epi$ below, relatively to the possible positions of the symbols of $\gamma$, $\delta$ and $\epsilon$, there is a $(3,2)$-sequence.
    (2.b.i) $\epi=(a\dots h\dots c\dots b\dots f\dots e\dots g\dots d\dots i\dots )$. $\tau_1=(a\;b\;d)$, $\tau_2=(g\;h\;i)$, $\tau_3=(a\;e\;c)$
    (2.b.ii) $\epi=(a\dots i\dots c\dots h\dots b\dots f\dots e\dots g\dots d\dots )$. $\tau_1=(g\;i\;h)$, $\tau_2=(a\;b\;c)$, $\tau_3=(g\;i\;h)$
    (2.b.iii) $\epi=(a\dots c\dots h\dots b\dots f\dots e\dots g\dots d\dots i\dots )$. $\tau_1=(a\;b\;d)$, $\tau_2=(g\;h\;i)$, $\tau_3=(c\;f\;d)$
    (2.b.iv) $\epi=(a\dots i\dots c\dots b\dots h\dots f\dots e\dots g\dots d\dots )$. $\tau_1=(c\;f\;d)$, $\tau_2=(g\;h\;i)$, $\tau_3=(a\;b\;f)$
    (2.b.v) $\epi=(a\dots c\dots b\dots i\dots f\dots h\dots e\dots g\dots d\dots )$. $\tau_1=(g\;i\;h)$, $\tau_2=(d\;e\;f)$, $\tau_3=(g\;i\;h)$
    (2.b.vi) $\epi=(a\dots i\dots c\dots f\dots b\dots e\dots h\dots g\dots d\dots )$. $\tau_1=(d\;i\;f)$, $\tau_2=(e\;h\;i)$, $\tau_3=(a\;b\;c)$
    (2.b.vii) $\epi=(a\dots c\dots i\dots f\dots b\dots e\dots h\dots g\dots d\dots )$. $\tau_1=(a\;i\;g)$, $\tau_2=(b\;h\;i)$, $\tau_3=(d\;e\;f)$
    (2.b.viii) $\epi=(a\dots c\dots f\dots i\dots b\dots e\dots h\dots g\dots d\dots )$. $\tau_1=(a\;i\;g)$, $\tau_2=(d\;e\;f)$, $\tau_3=(b\;h\;i)$
    (2.b.ix) $\epi=(a\dots c\dots i\dots f\dots b\dots h\dots e\dots g\dots d\dots )$. $\tau_1=(d\;f\;e)$, $\tau_2=(g\;h\;i)$, $\tau_3=(d\;f\;e)$
    (2.b.x) $\epi=(a\dots i\dots c\dots f\dots b\dots h\dots e\dots g\dots d\dots )$. $\tau_1=(d\;f\;e)$, $\tau_2=(g\;h\;i)$, $\tau_3=(d\;f\;e)$
    (2.b.xi) $\epi=(a\dots i\dots c\dots f\dots h\dots b\dots e\dots g\dots d\dots )$. $\tau_1=(d\;f\;e)$, $\tau_2=(g\;h\;i)$, $\tau_3=(d\;f\;e)$
    (2.b.xii) $\epi=(a\dots c\dots i\dots f\dots h\dots b\dots e\dots g\dots d\dots )$. $\tau_1=(a\;f\;d)$, $\tau_2=(b\;c\;f)$, $\tau_3=(g\;h\;i)$
    (2.b.xiii) $\epi=(a\dots c\dots i\dots h\dots f\dots b\dots e\dots g\dots d\dots )$. $\tau_1=(a\;i\;g)$, $\tau_2=(b\;c\;i)$, $\tau_3=(d\;e\;f)$
    (2.b.xiv) $\epi=(a\dots h\dots c\dots f\dots b\dots e\dots g\dots d\dots i\dots )$. $\tau_1=(d\;i\;f)$, $\tau_2=(f\;g\;h)$, $\tau_3=(a\;b\;c)$
    (2.b.xv) $\epi=(a\dots i\dots f\dots c\dots h\dots e\dots b\dots g\dots d\dots )$. $\tau_1=(d\;f\;e)$, $\tau_2=(a\;b\;c)$, $\tau_3=(d\;f\;e)$

Proposition 40: If $\Gamma$ is a component of $\spi$, then the product $\Gamma\epi$ is a $(n+1)$-cycle.

Proof. Suppose that $\spi=\Sigma\Gamma$. We have two cases:
(1) $\Sigma=\iota$. Then $\Gamma=\spi$ and $\spi\epi=\sigma$. As $\sigma$ is a $(n+1)$-cycle, the proposition holds.
(2) $\Sigma\neq\iota$ and $Supp(\Gamma)\cap Supp(\Sigma)=\emptyset$. As the cycles of $\Gamma$ do not intersect or interleave any cycle of $\Sigma$, then w.l.o.g assume $\epi=(\gamma_1\;\gamma_2\dots\gamma_r\;a\dots)$ and $Supp(\Gamma)=\{\gamma_1,\gamma_2,\dots,\gamma_r\}$, where $a \in Supp(\Sigma)$. Suppose, by contradiction, that $\Gamma\epi$ is not a $(n+1)$-cycle. In this case, $\Gamma\epi$ is a product of disjoint cycles containing a cycle $(\gamma_r\;a\dots)$ and this is the only cycle of $\Gamma\epi$ containing symbols of $Supp(\Sigma)$. However, this implies that $\Sigma\Gamma\epi=\spi\epi=\sigma$ is not a $(n+1)$-cycle, which is impossible.