Kernelization hardness for crossing number with prescribed rotation systems

From papers

Let GG be a graph with a given rotation system, and let k1k\geq 1 be an integer. A drawing of GG respecting the prescribed rotation system is one in which the clockwise order of the edges incident with every vertex agrees with the given rotation. The crossing number problem asks whether such a drawing has at most kk crossings. Kernelization-hardness conjecture. The problem of deciding whether GG has a drawing respecting the prescribed rotation system with at most kk crossings, parameterized by kk, does not admit a polynomial kernel unless NPcoNP/poly\operatorname{NP}\subseteq\operatorname{coNP/poly}. Consequently, the crossing number problem restricted to cubic graphs, and the analogous minor crossing number problem, do not admit a polynomial kernel with respect to kk unless NPcoNP/poly\operatorname{NP}\subseteq\operatorname{coNP/poly}. The paper proves the corresponding lower bound for almost-planar graphs without prescribed rotation systems; this proposed strengthening would extend the obstruction to graphs with prescribed rotations and, consequently, to cubic and minor crossing number. Its status is left open by the source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Petr Hliněný and Marek Derňár, “Crossing Number is Hard for Kernelization”, arXiv:1512.02379 (2016).

Solutions 0

No solutions have been posted yet.