Document Open Access Logo

Fine-Grained Complexity of Coloring Unit Disks and Balls

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2017.18.pdf
  • Filesize: 0.79 MB
  • 16 pages

Document Identifiers

Subject Classification

Keywords
  • unit disk graphs
  • unit ball graphs
  • coloring
  • exact algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, and Pawel Rzazewski. Fine-Grained Complexity of Coloring Unit Disks and Balls. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.18

Author Details

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

References

  1. Jochen Alber and Jirí Fiala. Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms, 52(2):134-151, 2004. URL: http://dx.doi.org/10.1016/j.jalgor.2003.10.001.
  2. Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, and Dániel Marx. Tight bounds for Planar Strongly Connected Steiner Subgraph with fixed number of terminals (and extensions). In SODA 2014 Proc., pages 1782-1801, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.129.
  3. Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub W. Pachocki, and Arkadiusz Socała. Tight lower bounds on graph embedding problems. CoRR, abs/1602.05016, 2016. URL: http://arxiv.org/abs/1602.05016.
  4. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Bidimensional parameters and local treewidth. SIAM J. Discrete Math., 18(3):501-511, 2004. URL: http://dx.doi.org/10.1137/S0895480103433410.
  5. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Fixed-parameter algorithms for (k,r)-Center in planar graphs and map graphs. ACM Transactions on Algorithms, 1(1):33-47, 2005. URL: http://dx.doi.org/10.1145/1077464.1077468.
  6. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866-893, 2005. URL: http://dx.doi.org/10.1145/1101821.1101823.
  7. Erik D. Demaine and Mohammad Taghi Hajiaghayi. Fast algorithms for hard graph problems: Bidimensionality, minors, and local treewidth. In GD 2014 Proc., pages 517-533, 2004. URL: http://dx.doi.org/10.1007/978-3-540-31843-9_57.
  8. Erik D. Demaine and MohammadTaghi Hajiaghayi. The bidimensionality theory and its algorithmic applications. Comput. J., 51(3):292-302, 2008. URL: http://dx.doi.org/10.1093/comjnl/bxm033.
  9. Erik D. Demaine and MohammadTaghi Hajiaghayi. Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica, 28(1):19-36, 2008. URL: http://dx.doi.org/10.1007/s00493-008-2140-4.
  10. Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs. In STACS 2010 Proc., pages 251-262, 2010. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2459.
  11. Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos. Subexponential parameterized algorithms. Computer Science Review, 2(1):29-39, 2008. URL: http://dx.doi.org/10.1016/j.cosrev.2008.02.004.
  12. Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender, and Fedor V. Fomin. Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions. Algorithmica, 58(3):790-810, 2010. URL: http://dx.doi.org/10.1007/s00453-009-9296-1.
  13. Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Yngve Villanger. Tight bounds for parameterized complexity of cluster editing with a small number of clusters. J. Comput. Syst. Sci., 80(7):1430-1447, 2014. URL: http://dx.doi.org/10.1016/j.jcss.2014.04.015.
  14. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Subexponential algorithms for partial cover problems. Inf. Process. Lett., 111(16):814-818, 2011. URL: http://dx.doi.org/10.1016/j.ipl.2011.05.016.
  15. Fedor V. Fomin and Dimitrios M. Thilikos. Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput., 36(2):281-309, 2006. URL: http://dx.doi.org/10.1137/S0097539702419649.
  16. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  17. Philip N. Klein and Dániel Marx. Solving Planar k-Terminal Cut in O(n^c√k) time. In ICALP 2012 Proc., pages 569-580, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_48.
  18. Philip N. Klein and Dániel Marx. A subexponential parameterized algorithm for Subset TSP on planar graphs. In SODA 2014 Proc., pages 1812-1830, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.131.
  19. J. Kratochvíl and J. Matoušek. Intersection graphs of segments. Journal of Combinatorial Theory, Series B, 62(2):289-315, 1994. URL: http://dx.doi.org/10.1006/jctb.1994.1071.
  20. Dániel Marx. Efficient approximation schemes for geometric problems? In ESA 2005 Proc., pages 448-459, 2005. URL: http://dx.doi.org/10.1007/11561071_41.
  21. Dániel Marx and Michal Pilipczuk. Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. In Nikhil Bansal and Irene Finocchi, editors, ESA 2015 Proc., volume 9294 of LNCS, pages 865-877. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_72.
  22. Dániel Marx and Anastasios Sidiropoulos. The Limited Blessing of Low Dimensionality: When 1-1/D is the Best Possible Exponent for D-dimensional Geometric Problems. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SOCG 2014 Proc., pages 67:67-67:76, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2582112.2582124.
  23. Gary L. Miller, Shang-Hua Teng, William Thurston, and Stephen A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. J. ACM, 44(1):1-29, January 1997. URL: http://dx.doi.org/10.1145/256292.256294.
  24. Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Subexponential-time parameterized algorithm for Steiner Tree on planar graphs. In STACS 2013 Proc., pages 353-364, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2013.353.
  25. Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Network sparsification for steiner problems on planar and bounded-genus graphs. In FOCS 2014 Proc., pages 276-285. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.37.
  26. W. D. Smith and N. C. Wormald. Geometric separator theorems. available online at URL: https://www.math.uwaterloo.ca/~nwormald/papers/focssep.ps.gz.
  27. W. D. Smith and N. C. Wormald. Geometric separator theorems and applications. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS 1998 Proc., pages 232-243, Washington, DC, USA, 1998. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=795664.796397.
  28. Dimitrios M. Thilikos. Fast sub-exponential algorithms and compactness in planar graphs. In ESA 2011 Proc., pages 358-369, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_31.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact