Crossing Number is Hard for Kernelization
| Authors | |
|---|---|
| Year of publication | 2016 |
| Type | Article in Proceedings |
| Conference | 32nd International Symposium on Computational Geometry (SoCG 2016) |
| MU Faculty or unit | |
| Citation | |
| Web | http://socg2016.cs.tufts.edu/ |
| Doi | http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.42 |
| Field | Informatics |
| Keywords | crossing number; kernelization; parameterized complexity |
| Description | 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. |
| Related projects: |