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 ∈ 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 O( √ 1) . The existence of a subexponential fixed-parameter algorithm for two layers immediately raises the question of whether this phenomenon is specific to two layers or can be extended to more layers. (In this setting, vertices are divided into h independent sets V 1 , . . . , V h , and the question is whether G admits an h-layered drawing with at most k crossings.) Here, we delve into highly technical depths of the topic of layered drawings to answer this question almost completely, by providing a subexponential fixed-parameter algorithm for three layers with running time 2 O(k 0.67 ) + n • k O(1) , and proving that there does not exist a 2 O(k 1-ϵ ) • n O(1)time algorithm (for any fixed ϵ > 0) for five or more layers, under the Exponential-Time Hypothesis.

Next to the question of subexponential-time algorithms, lies the question of the existence of polynomial kernels for h-layered crossing minimization. We completely resolve this question as well -while a polynomial kernel was already known for h = 2, we derive a new polynomial kernel for h = 3. Complementarily, we rule out the existence of a polynomial kernel for any h ≥ 4, assuming that the polynomial hierarchy does not collapse. Thus, we establish a complete dichotomy regarding polynomial kernelization based on the number of layers h.