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

The starting point of our work is the decade-old open question concerning the subexponential parameterized complexity of the 2-Layer Crossing Minimization problem. In this problem, the input is an \(n\)-vertex graph \(G\) whose vertices are divided into two independent sets \(V_1, V_2\), and a non-negative integer \(k\). The question is whether \(G\) supports a 2-layered drawing with at most \(k\) crossings. Here, a 2-layered drawing refers to a drawing of \(G\) where each set \(V_i\) for \(i \in \{1,2\}\) is placed on a distinct straight line parallel to the \(x\)-axis, and all edges are drawn as straight lines connecting vertices. Our first theorem resolves the aforementioned question in the affirmative by providing a fixed-parameter tractable (FPT) subexponential algorithm with running time \(2^{\mathcal O(\sqrt{k}\log k)} + n \cdot k^{\mathcal O(1)}\).