## Fine-Grained Complexity of Coloring Unit Disks and Balls

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

#### 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.
 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 series Journal of Computational Geometry, ISSN 1920-180X, (0 pkt) Issue year 2018 Vol 9 No 2 Pages 47-80 Publication size in sheets 0.3 Keywords in Polish kolorowanie, grafy przecięć dysków, ETH Keywords in English coloring, disk graphs, ETH Abstract in Polish W 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. DOI DOI:10.20382/jocg.v9i2a4 URL http://jocg.org/index.php/jocg/article/view/414 Language en angielski Score (nominal) 5 Score source journalList Score Ministerial score = 5.0, 20-10-2019, ArticleFromJournal Publication indicators WoS Citations = 0 Citation count*
 Cite 