Block Sorting: A Characterization and some Heuristics

NEW

Problem: Reconstructed conjecture: let $\operatorname{sc}(\pi)$ be the maximum size of a strongly compatible edge set in the order graph $G_\pi$ of a finite permutation $\pi\in S_n$. Since a compatible set of size $s$ yields a block-sorting sequence of length $n-1-s$, the conjecture most naturally means:

Equivalently, at least one of $\pi,\pi^{-1}$ always has a strong compatible set large enough to give a better-than-2 approximation. This is the formal reading supported by the paper’s surrounding discussion of approximation ratios from compatible/strongly compatible sets.

Result: The conjecture is false. In fact, even the weaker strict claim with factor $<2$ fails.

For $r\ge2$, set $n=2r+2$ and define

Then $\pi_r^{-1}=\pi_r$. Its blocks are

Moving the block $2\cdots r+1$ immediately after $1$ sorts the permutation, so $\operatorname{bs}(\pi_r)=1$.

Now compute $\operatorname{sc}(\pi_r)$. Let

A strongly compatible set of size $n-3=2r-1$ is

It is strong because $(1,n)$ contains all other listed edges both by value and by position, and the remaining unit edges lie in disjoint chains.

Conversely, no strongly compatible set can have size $n-2$ or $n-1$. In any compatible set, edges form vertex-disjoint directed paths. No path can contain vertices from both $L$ and $H$: edges from $L$ to $H$ are absent because their positions are reversed, and edges from $H$ to $L$ are impossible by value order. Thus a set of size $n-2$ would have exactly two path components, one covering all of $L$ and one covering all of $H$, with two extra edges attaching $1$ and/or $n$. The only possibilities force one of the following forbidden configurations:

• $(1,2)$ together with the $H$-unit edges: $(1,2)$ contains them by position but not by value;
• $(2r+1,n)$ together with the $L$-unit edges: same violation;
• $(1,2)$ and $(2r+1,n)$: they interleave by position;
• $(1,r+2)$ and $(r+1,n)$: they interleave by value.

Hence $\operatorname{sc}(\pi_r)=n-3$. Since $\pi_r^{-1}=\pi_r$,

But $\operatorname{bs}(\pi_r)=1$, so the ratio is exactly $2$. Therefore no better-than-2 guarantee can follow from taking the larger strong compatible set of $\pi$ and $\pi^{-1}$.

Citation: Definitions and context: Mahajan, Rama, and Vijayakumar, “Block Sorting: A Characterization and some Heuristics,” Nordic Journal of Computing, DOI 10.5555/1515784.1515790. The counterexample above is constructed here.