文章基本信息

标题：Crossing Number is Hard for Kernelization
本地全文：下载
作者：Petr Hlinen{\'y ; Marek Dern{\'a}r
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：51
页码：42:1-42:10
DOI：10.4230/LIPIcs.SoCG.2016.42
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：crossing number; tile crossing number; parameterized complexity; polynomial kernel; cross-composition