2025/10/15 by Fedor V. Fomin, Petr A. Golovach, Fomin, Fedor V. +7
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Infrastructure Maintenance and Monitoring #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2510.13335
openalex publication_date 2025/10/15 · openalex created_date 2025/10/17 · openalex updated_date 2026/07/30
The starting point of our work is a decade-old open question concerning the subexponential parameterized complexity of 2-Layer Crossing Minimization. In this problem, the input is an n-vertex graph G whose vertices are partitioned into two independent sets V1 and V2, and a non-negative integer k. The question is whether G admits a 2-layered drawing with at most k crossings, where each Vi 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 2O(√(k)log k) + n ⋅ kO(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 V1, …, Vh, 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(k2/3log k) + n ⋅ kO(1) for h = 3 layers. In contrast, we show that for all h ≥ 5, no algorithm with running time 2o(k/log k) ⋅ nO(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 ≥ 4 unless the polynomial hierarchy collapses.