DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2016.42

Crossing Number is Hard for Kernelization

Authors: Petr Hlinený and Marek Dernár

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

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.

Cite as

Petr Hlinený and Marek Dernár. Crossing Number is Hard for Kernelization. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 42:1-42:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hlineny_et_al:LIPIcs.SoCG.2016.42,
  author =	{Hlinen\'{y}, Petr and Dern\'{a}r, Marek},
  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 =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.42},
  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}
}

Search Results

Documents authored by Dernár, Marek

Crossing Number is Hard for Kernelization

Abstract

Cite as

Thanks for your feedback!

Could not send message