Crossing number is hard for kernelization

DOI10.4230/LIPICS.SOCG.2016.42MaRDI QIDQ3132876zbMATH OpenFDO

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

Publication date 30 January 2018

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

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)

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.

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?

Cited in

(7)

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

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)