Crossing number is hard for kernelization

DOI10.4230/LIPICS.SOCG.2016.42zbMATH Open1387.68181arXiv1512.02379MaRDI QIDQ3132876FDOQ3132876

Authors: Petr Hliněný, Marek Derňár 

Publication date: 30 January 2018

Abstract: The graph crossing number problem, cr(G)<=k, asks for a drawing of a graph G in the plane with at most k edge crossings. Although this problem is in general notoriously difficult, it is fixed- parameter tractable for the parameter k [Grohe]. This suggests a closely related question of whether this problem has a polynomial kernel, meaning whether every instance of cr(G)<=k can be in polynomial time reduced to an equivalent instance of size polynomial in k (and independent of |G|). We answer this question in the negative. Along the proof we show that the tile crossing number problem of twisted planar tiles is NP-hard, which has been an open problem for some time, too, and then employ the complexity technique of cross-composition. Our result holds already for the special case of graphs obtained from planar graphs by adding one edge.

Full work available at URL: https://arxiv.org/abs/1512.02379

Recommendations

• Adding one edge to planar graphs makes crossing number hard
• Crossing number is hard for cubic graphs
• Mathematical Foundations of Computer Science 2004
• Crossing Numbers and Parameterized Complexity
• Which crossing number is it anyway?

zbMATH Keywords

parameterized complexitypolynomial kernelcrossing numbercross-compositiontile crossing number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (6)

• Crossing minimization in perturbed drawings
• Deciding Parity of Graph Crossing Number
• Connecting the dots (with minimum crossings)
• Structure and generation of crossing-critical graphs
• Parameterized analysis and crossing minimization problems
• Grid recognition: classical and parameterized computational perspectives

This page was built for publication: Crossing number is hard for kernelization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3132876)