Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1367505,
author = {Derňár, Marek and Hliněný, Petr},
address = {Germany},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
doi = {http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.42},
keywords = {crossing number; kernelization; parameterized complexity},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Germany},
isbn = {978-3-95977-009-5},
pages = {"42:1"-"42:10"},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
title = {Crossing Number is Hard for Kernelization},
url = {http://socg2016.cs.tufts.edu/},
year = {2016}
}
TY - JOUR
ID - 1367505
AU - Derňár, Marek - Hliněný, Petr
PY - 2016
TI - Crossing Number is Hard for Kernelization
PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
CY - Germany
SN - 9783959770095
KW - crossing number
KW - kernelization
KW - parameterized complexity
UR - http://socg2016.cs.tufts.edu/
L2 - http://socg2016.cs.tufts.edu/
N2 - 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.
ER -
DERŇÁR, Marek and Petr HLINĚNÝ. Crossing Number is Hard for Kernelization. Online. In \textit{32nd International Symposium on Computational Geometry (SoCG 2016)}. Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2016, p.~''42:1''-''42:10'', 10 pp. ISBN~978-3-95977-009-5. Available from: https://dx.doi.org/10.4230/LIPIcs.SoCG.2016.42.
|
