Parameterized complexity of separable index

Question 1.3 · arXiv:2308.02981

arXiv Question high confidence— first stated 2023-08-06

Authors: Édouard Bonnet, Romain Bourneuf, Colin Geniet, Stéphan Thomassé

Status open high confidence

Question 1.3 asks for the parameterised complexity of computing the separable index sep(σ) — the smallest k such that a permutation σ factors as a product of k separable permutations — and of approximating it within a constant factor. The paper's main theorem (Theorem 1.1) yields an FPT approximation algorithm, but the approximation ratio is a triple-exponential function of the parameter k, which the authors note is very far from constant. No follow-up work addressing the exact complexity or a constant-factor approximation of sep(σ) has been found in the literature as of May 2026.

Reviewer notes. No follow-up found after three targeted searches and direct PDF inspection. The conjecture is recent (2023, published SODA 2024) and quite specific; open with high confidence. The arxiv:2507.07606 paper on Ramsey-like theorems for separable permutations was inspected but its abstract does not address the complexity of sep(σ).

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. What is the parameterised complexity of computing $\mathrm{sep}(\sigma)$, and of approximating it within a constant factor?

Context

The paper's main result implies an FPT approximation for the separable index $\mathrm{sep}(\sigma)$ via pattern recognition, but the approximation function is triple exponential in $k$. The authors ask whether the complexity of computing or approximating $\mathrm{sep}(\sigma)$ exactly can be improved, possibly to an exact algorithm.

Source paper

Factoring Pattern-Free Permutations into Separable ones
Édouard Bonnet, Romain Bourneuf, Colin Geniet, Stéphan Thomassé · 2023-08-06
https://arxiv.org/abs/2308.02981 PDF source