Crossing Number is Hard for Kernelization

DERŇÁR, Marek a 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, s. "42:1"-"42:10", 10 s. ISBN 978-3-95977-009-5. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.SoCG.2016.42.

Základní údaje

Originální název

Crossing Number is Hard for Kernelization

Název česky

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

Autoři

DERŇÁR, Marek (703 Slovensko, domácí) a Petr HLINĚNÝ (203 Česká republika, garant, domácí)

Vydání

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

Nakladatel

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/16:00088543

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-009-5

ISSN

DOI

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

Klíčová slova anglicky

crossing number; kernelization; parameterized complexity

Štítky

core_A, firank_A, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

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.

Česky

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.

---

Návaznosti

GA14-03501S, projekt VaV	Název: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky Investor: Grantová agentura ČR, Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
MUNI/A/0935/2015, interní kód MU	Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU) Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/0945/2015, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace V. Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace V., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty