Kernelization hardness for crossing number with prescribed rotation systems

About 11 years old · traced to

Let GG be a graph with a given rotation system, and let k≥1k\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 NP⁡⊆coNP/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 NP⁡⊆coNP/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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.