Crossing Number is Hard for Kernelization

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

DERŇÁR Marek HLINĚNÝ Petr

Year of publication 2016
Type Article in Proceedings
Conference 32nd International Symposium on Computational Geometry (SoCG 2016)
MU Faculty or unit

Faculty of Informatics

Citation
Web http://socg2016.cs.tufts.edu/
Doi http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.42
Field Informatics
Keywords crossing number; kernelization; parameterized complexity
Description 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, STOC 2001]. 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info