License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.18
URN: urn:nbn:de:0030-drops-71800
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7180/
Go to the corresponding LIPIcs Volume Portal


Biró, Csaba ; Bonnet, Édouard ; Marx, Dániel ; Miltzow, Tillmann ; Rzazewski, Pawel

Fine-Grained Complexity of Coloring Unit Disks and Balls

pdf-format:
LIPIcs-SoCG-2017-18.pdf (0.8 MB)


Abstract

On planar graphs, many classic algorithmic problems enjoy a certain "square root phenomenon" and can be solved significantly faster than what is known to be possible on general graphs: for example, Independent Set, 3-Coloring, Hamiltonian Cycle, Dominating Set can be solved in time 2^O(sqrt{n}) on an n-vertex planar graph, while no 2^o(n) algorithms exist for general graphs, assuming the Exponential Time Hypothesis (ETH). The square root in the exponent seems to be best possible for planar graphs: assuming the ETH, the running time for these problems cannot be improved to 2^o(sqrt{n}). In some cases, a similar speedup can be obtained for 2-dimensional geometric problems, for example, there are 2^O(sqrt{n}log n) time algorithms for Independent Set on unit disk graphs or for TSP on 2-dimensional point sets. In this paper, we explore whether such a speedup is possible for geometric coloring problems. On the one hand, geometric objects can behave similarly to planar graphs: 3-Coloring can be solved in time 2^O(sqrt{n}) on the intersection graph of n unit disks in the plane and, assuming the ETH, there is no such algorithm with running time 2^o(sqrt{n}). On the other hand, if the number L of colors is part of the input, then no such speedup is possible: Coloring the intersection graph of n unit disks with L colors cannot be solved in time 2^o(n), assuming the ETH. More precisely, we exhibit a smooth increase of complexity as the number L of colors increases: If we restrict the number of colors to L=Theta(n^alpha) for some 0<=alpha<=1, then the problem of coloring the intersection graph of n unit disks with L colors * can be solved in time exp(O(n^{{1+alpha}/2}log n))=exp( O(sqrt{nL}log n)), and * cannot be solved in time exp(o(n^{{1+alpha}/2}))=exp(o(sqrt{nL})), unless the ETH fails. More generally, we consider the problem of coloring d-dimensional unit balls in the Euclidean space and obtain analogous results showing that the problem * can be solved in time exp(O(n^{{d-1+alpha}/d}log n))=exp(O(n^{1-1/d}L^{1/d}log n)), and * cannot be solved in time exp(n^{{d-1+alpha}/d-epsilon})= exp (O(n^{1-1/d-epsilon}L^{1/d})) for any epsilon>0, unless the ETH fails.

BibTeX - Entry

@InProceedings{bir_et_al:LIPIcs:2017:7180,
  author =	{Csaba Bir{\'o} and {\'E}douard Bonnet and D{\'a}niel Marx and Tillmann Miltzow and Pawel Rzazewski},
  title =	{{Fine-Grained Complexity of Coloring Unit Disks and Balls}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7180},
  URN =		{urn:nbn:de:0030-drops-71800},
  doi =		{10.4230/LIPIcs.SoCG.2017.18},
  annote =	{Keywords: unit disk graphs, unit ball graphs, coloring, exact algorithm}
}

Keywords: unit disk graphs, unit ball graphs, coloring, exact algorithm
Seminar: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 08.06.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI