License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.48
URN: urn:nbn:de:0030-drops-187017
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18701/
Fomin, Fedor V. ;
Golovach, Petr A. ;
Inamdar, Tanmay ;
Saurabh, Saket ;
Zehavi, Meirav
Kernelization for Spreading Points
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.
BibTeX - Entry
@InProceedings{fomin_et_al:LIPIcs.ESA.2023.48,
author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav},
title = {{Kernelization for Spreading Points}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {48:1--48:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18701},
URN = {urn:nbn:de:0030-drops-187017},
doi = {10.4230/LIPIcs.ESA.2023.48},
annote = {Keywords: parameterized algorithms, kernelization, spreading points, distant representatives, unit disk packing}
}
|
Keywords: |
|
parameterized algorithms, kernelization, spreading points, distant representatives, unit disk packing |
|
Collection: |
|
31st Annual European Symposium on Algorithms (ESA 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
30.08.2023 |
