Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization

The starting point of our work is a decade-old open question concerning the subexponential parameterized complexity of $\text{textsc}2-LayerCrossingMinimization$. In this problem, the input is an $n$-vertex graph $G$ whose vertices are partitioned into two independent sets $V_1$ and $V_2$, and a non-negative integer $k$. The question is whether $G$ admits a 2-layered drawing with at most $k$ crossings, where each $V_i$ lies on a distinct line parallel to the $x$-axis, and all edges are straight lines. We resolve this open question by giving the first subexponential fixed-parameter algorithm for this problem, running in time $2^{O(\sqrt{k}\log k)}+n\cdot k^{O(1)}$. We then ask whether the subexponential phenomenon extends beyond two layers. In the general $h$-Layer Crossing Minimization problem, the vertex set is partitioned into $h$ independent sets $V_1,\dots ,V_h$, and the goal is to decide whether an $h$-layered drawing with at most $k$ crossings exists. We present a subexponential FPT algorithm for three layers with running time $2^{O(k^{2\mathrm{/}3}\log k)}+n\cdot k^{O(1)}$ for $h=3$ layers. In contrast, we show that for all $h\ge 5$, no algorithm with running time $2^{o(k\mathrm{/}\log k)}\cdot n^{O(1)}$ exists unless the Exponential-Time Hypothesis fails. Finally, we address polynomial kernelization. While a polynomial kernel was already known for $h=2$, we design a new polynomial kernel for $h=3$. These kernels are essential ingredients in our subexponential algorithms. Finally, we rule out polynomial kernels for all $h\ge 4$ unless the polynomial hierarchy collapses.