$ \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:

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:

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:

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 an $N$-cycle.

Proof. Write $\spi=\Sigma\Gamma$, where $\Sigma$ is the product of the nontrivial cycles outside $\Gamma$. If $\Sigma=\iota$, then $\Gamma=\spi$, and hence \[ \Gamma\epi=\spi\epi=\eiota, \] which is an $N$-cycle. Assume henceforth that $\Sigma\ne\iota$. For $U\subseteq E_N$, call each maximal sequence in $E_N\setminus U$ consecutive under $\epi^{-1}$ a $U$-gap. Fix a cycle $\mathsf{D}$ of $\Sigma$. The support of every cycle $\mathsf{C}$ of $\Gamma$ lies in one $\Supp(\mathsf{D})$-gap: otherwise, some consecutive pair $(a,b)$ of $\mathsf{C}$ separates two symbols of $\mathsf{D}$, and some consecutive pair $(d,e)$ of $\mathsf{D}$ crosses the resulting intervals. Thus \[ \epi^{-1}=(a\ \dots\ e\ \dots\ b\ \dots\ d\ \dots), \] so $\mathsf{C}$ and $\mathsf{D}$ intersect, a contradiction. Furthermore, cycles lying in distinct $\Supp(\mathsf{D})$-gaps cannot intersect. The connectedness of $\Gamma$ therefore places all of $\Supp(\Gamma)$ in one such gap, and hence places $\Supp(\mathsf{D})$ in one $\Supp(\Gamma)$-gap.
Set $\alpha=\Gamma\epi$. Because $\Gamma$ fixes every symbol outside $\Supp(\Gamma)$, each $\Supp(\Gamma)$-gap is contained in a single cycle of $\alpha$. By the preceding, the support of each nontrivial cycle $\mathsf{D}$ of $\Sigma$ is therefore contained in a single cycle of $\alpha$. Since $\mathsf{D}$ fixes every symbol outside its support, it cannot send a symbol from one cycle of $\alpha$ to another. The nontrivial cycles of $\Sigma$ are disjoint, so neither can $\Sigma$. Consequently, left multiplication by $\Sigma$ cannot merge distinct cycles of $\alpha$. Since \[ \Sigma\alpha=\Sigma\Gamma\epi=\spi\epi=\eiota \] is an $N$-cycle, $\alpha$ cannot have more than one cycle. Therefore $\Gamma\epi=\alpha$ is an $N$-cycle.