License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.42
URN: urn:nbn:de:0030-drops-59347
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5934/
Go to the corresponding LIPIcs Volume Portal

Hlinený, Petr ; Dernár, Marek

Crossing Number is Hard for Kernelization

pdf-format:
LIPIcs-SoCG-2016-42.pdf (0.5 MB)

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, 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.

BibTeX - Entry

@InProceedings{hlinen_et_al:LIPIcs:2016:5934,
  author =	{Petr Hlinen{\'y} and Marek Dern{\'a}r},
  title =	{{Crossing Number is Hard for Kernelization}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{42:1--42:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{S{\'a}ndor Fekete and Anna Lubiw},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5934},
  URN =		{urn:nbn:de:0030-drops-59347},
  doi =		{10.4230/LIPIcs.SoCG.2016.42},
  annote =	{Keywords: crossing number; tile crossing number; parameterized complexity; polynomial kernel; cross-composition}
}

Keywords: crossing number; tile crossing number; parameterized complexity; polynomial kernel; cross-composition
Collection: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date: 2016
Date of publication: 10.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI