Kernelization for Spreading Points

Authors Fedor V. Fomin , Petr A. Golovach , Tanmay Inamdar , Saket Saurabh, Meirav Zehavi



PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.48.pdf
  • Filesize: 0.95 MB
  • 16 pages

Document Identifiers

Author Details

Fedor V. Fomin
  • University of Bergen, Norway
Petr A. Golovach
  • University of Bergen, Norway
Tanmay Inamdar
  • University of Bergen, Norway
Saket Saurabh
  • Institute of Mathematical Sciences, Chennai, India
  • University of Bergen, Norway
Meirav Zehavi
  • Ben-Gurion University, Beer-Sheva, Israel

Acknowledgements

We thank the anonymous reviewers for their valuable comments.

Cite AsGet BibTex

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Kernelization for Spreading Points. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.48

Abstract

We consider the following problem about dispersing points. Given a set of points in the plane, the task is to identify whether by moving a small number of points by small distance, we can obtain an arrangement of points such that no pair of points is "close" to each other. More precisely, for a family of n points, an integer k, and a real number d > 0, we ask whether at most k points could be relocated, each point at distance at most d from its original location, such that the distance between each pair of points is at least a fixed constant, say 1. A number of approximation algorithms for variants of this problem, under different names like distant representatives, disk dispersing, or point spreading, are known in the literature. However, to the best of our knowledge, the parameterized complexity of this problem remains widely unexplored. We make the first step in this direction by providing a kernelization algorithm that, in polynomial time, produces an equivalent instance with 𝒪(d²k³) points. As a byproduct of this result, we also design a non-trivial fixed-parameter tractable (FPT) algorithm for the problem, parameterized by k and d. Finally, we complement the result about polynomial kernelization by showing a lower bound that rules out the existence of a kernel whose size is polynomial in k alone, unless NP ⊆ coNP/poly.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • parameterized algorithms
  • kernelization
  • spreading points
  • distant representatives
  • unit disk packing

Metrics

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

References

  1. Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry. Springer, Berlin, Heidelberg, 2009. Google Scholar
  2. Christoph Baur and S'andor P Fekete. Approximation of geometric dispersion problems. Algorithmica, 30(3):451-470, 2001. Google Scholar
  3. Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky, and Graeme Stroud. Distant Representatives for Rectangles in the Plane. In 29th Annual European Symposium on Algorithms (ESA), volume 204 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.17.
  4. Sergio Cabello. Approximation algorithms for spreading points. J. Algorithms, 62(2):49-73, 2007. URL: https://doi.org/10.1016/j.jalgor.2004.06.009.
  5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  6. Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, and Morteza Zadimoghaddam. Minimizing movement. ACM Trans. Algorithms, 5(3):30:1-30:30, 2009. URL: https://doi.org/10.1145/1541885.1541891.
  7. Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Dániel Marx. Minimizing movement: Fixed-parameter tractability. ACM Trans. Algorithms, 11(2):14:1-14:29, 2014. URL: https://doi.org/10.1145/2650247.
  8. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  9. Srinivas Doddi, Madhav V. Marathe, Andy Mirzaian, Bernard M. E. Moret, and Binhai Zhu. Map labeling and its generalizations. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 148-157. ACM/SIAM, 1997. URL: http://dl.acm.org/citation.cfm?id=314161.314250.
  10. Adrian Dumitrescu and Minghui Jiang. Dispersion in unit disks. In 27th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 5 of Leibniz International Proceedings in Informatics (LIPIcs), pages 299-310, Dagstuhl, Germany, 2010. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2010.2464.
  11. Adrian Dumitrescu and Minghui Jiang. Constrained k-center and movement to independence. Discret. Appl. Math., 159(8):859-865, 2011. URL: https://doi.org/10.1016/j.dam.2011.01.008.
  12. Adrian Dumitrescu and Minghui Jiang. Dispersion in disks. Theory Comput. Syst., 51(2):125-142, 2012. URL: https://doi.org/10.1007/s00224-011-9331-x.
  13. S'andor P Fekete and Henk Meijer. Maximum dispersion and geometric maximum weight cliques. Algorithmica, 38(3):501-511, 2004. Google Scholar
  14. Jirí Fiala, Jan Kratochvíl, and Andrzej Proskurowski. Systems of distant representatives. Discret. Appl. Math., 145(2):306-316, 2005. URL: https://doi.org/10.1016/j.dam.2004.02.018.
  15. Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. (re)packing equal disks into rectangle. CoRR, abs/2211.09603, 2022. URL: https://doi.org/10.48550/ARXIV.2211.09603.
  16. Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, and Meirav Zehavi. (re)packing equal disks into rectangle. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 60:1-60:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.60.
  17. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of parameterized preprocessing. Cambridge University Press, Cambridge, 2019. Google Scholar
  18. Tien-Ruey Hsiang, Esther M Arkin, Michael A Bender, Sandor Fekete, and Joseph SB Mitchell. Online dispersion algorithms for swarms of robots. In Proceedings of the nineteenth annual symposium on Computational geometry, pages 382-383, 2003. Google Scholar
  19. Tien-Ruey Hsiang, Esther M Arkin, Michael A Bender, S'andor P Fekete, and Joseph SB Mitchell. Algorithms for rapidly dispersing robot swarms in unknown environments. In Algorithmic Foundations of Robotics V, pages 77-93. Springer, 2004. Google Scholar
  20. Minghui Jiang. A new approximation algorithm for labeling points with circle pairs. Inf. Process. Lett., 99(4):125-129, 2006. URL: https://doi.org/10.1016/j.ipl.2006.04.006.
  21. Minghui Jiang, Jianbo Qian, Zhongping Qin, Binhai Zhu, and Robert J. Cimikowski. A simple factor-3 approximation for labeling points with circles. Inf. Process. Lett., 87(2):101-105, 2003. URL: https://doi.org/10.1016/S0020-0190(03)00256-4.
  22. Maarten Löffler and Marc J. van Kreveld. Largest bounding box, smallest diameter, and related problems on imprecise points. Comput. Geom., 43(4):419-433, 2010. URL: https://doi.org/10.1016/j.comgeo.2009.03.007.
  23. Farnaz Sheikhi, Ali Mohades, Mark de Berg, and Ali D. Mehrabi. Separability of imprecise points. Comput. Geom., 61:24-37, 2017. URL: https://doi.org/10.1016/j.comgeo.2016.10.001.
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