Kernelization hardness for crossing number with prescribed rotation systems
Kernelization hardness for crossing number with prescribed rotation systems
Let be a graph with a given rotation system, and let be an integer. A drawing of 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 crossings. Kernelization-hardness conjecture. The problem of deciding whether has a drawing respecting the prescribed rotation system with at most crossings, parameterized by , does not admit a polynomial kernel unless . 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 unless . 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
Sign in to submit a solution.
No solutions have been posted yet.