Crossing Number is Hard for Kernelization

D 2016

Crossing Number is Hard for Kernelization

DERŇÁR, Marek and Petr HLINĚNÝ

Basic information

Original name

Crossing Number is Hard for Kernelization

Name in Czech

Průsečíkové číslo je těžké kernelizovat

Authors

DERŇÁR, Marek (703 Slovakia, belonging to the institution) and Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution)

Edition

Germany, 32nd International Symposium on Computational Geometry (SoCG 2016), p. "42:1"-"42:10", 10 pp. 2016

Publisher

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

References:

URL

RIV identification code

RIV/00216224:14330/16:00088543

Organization unit

Faculty of Informatics

ISBN

978-3-95977-009-5

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.42

Keywords in English

crossing number; kernelization; parameterized complexity

Abstract

ORIG CZ

V originále

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.

In Czech

Dokážeme, že problém průsečíkového čísla grafu nelze polynomiálně kernelizovat, což znamená, že nelze danou instanci v polynomiálním čase převést na ekvivalentní instanci polynomiální velikosti v parametru k.

Links

GA14-03501S, research and development project

Name: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky

Investor: Czech Science Foundation

MUNI/A/0935/2015, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Acronym: SKOMU)

Investor: Masaryk University, Category A

MUNI/A/0945/2015, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace V.

Investor: Masaryk University, Category A

Citovat

DERŇÁR, Marek and Petr HLINĚNÝ. Crossing Number is Hard for Kernelization. Online. In 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.

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

Detailed Information on Publication Record