Fine-Grained Complexity of Coloring Unit Disks and Balls

Csaba Biro , Edouard Bonnet , Daniel Marx , Tillmann Miltzow , Paweł Rzążewski


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.
Author Csaba Biro
Csaba Biro,,
, Edouard Bonnet
Edouard Bonnet,,
, Daniel Marx
Daniel Marx,,
, Tillmann Miltzow
Tillmann Miltzow,,
, Paweł Rzążewski (FMIS / DIPS)
Paweł Rzążewski,,
- Department of Information Processing Systems
Journal seriesJournal of Computational Geometry, ISSN 1920-180X, (0 pkt)
Issue year2018
Publication size in sheets0.3
Keywords in Polishkolorowanie, grafy przecięć dysków, ETH
Keywords in Englishcoloring, disk graphs, ETH
Abstract in PolishW pracy rozważamy problem kolorowania grafu przecięć n dysków na k kolorów (k może być funkcją n). Pokazujemy, że problem ten można rozwiązać w czasie 2^O(sqrt(nk) log n), a istnienie algorytmu działającego w czasie 2^o(sqrt(nk)) przeczyłoby ETH. Ponadto rozszerzamy te wyniki na grafy przecięć d-wymiarowych kul.
Languageen angielski
Score (nominal)5
ScoreMinisterial score = 5.0, 22-05-2019, ArticleFromJournal
Publication indicators WoS Citations = 0
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.