{"ID":2855097,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.13335","arxiv_id":"2510.13335","title":"Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization","abstract":"The starting point of our work is a decade-old open question concerning the subexponential parameterized complexity of \\textsc{2-Layer Crossing Minimization}. 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, \\ldots, 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/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/\\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.","short_abstract":"The starting point of our work is a decade-old open question concerning the subexponential parameterized complexity of \\textsc{2-Layer Crossing Minimization}. 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$. T...","url_abs":"https://arxiv.org/abs/2510.13335","url_pdf":"https://arxiv.org/pdf/2510.13335v1","authors":"[\"Fedor V. Fomin\",\"Petr A. Golovach\",\"Tanmay Inamdar\",\"Saket Saurabh\",\"Meirav Zehavi\"]","published":"2025-10-15T09:19:26Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CG\"]","methods":"[]","has_code":false}