Document Open Access Logo

On Covering Segments with Unit Intervals

Authors Dan Bergren, Eduard Eiben , Robert Ganian, Iyad Kanj

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.13.pdf
  • Filesize: 0.6 MB
  • 17 pages

Document Identifiers

Author Details

Dan Bergren
  • School of Computing, DePaul University, Chicago, USA
Eduard Eiben
  • Department of Computer Science, Royal Holloway, University of London, Egham, UK
Robert Ganian
  • Algorithms and Complexity Group, Vienna University of Technology, Vienna, Austria
Iyad Kanj
  • School of Computing, DePaul University, Chicago, USA

Funding

  • Ganian, Robert: Robert Ganian acknowledges support by the Austrian Science Fund (FWF, project P31336).

Cite As Get BibTex

Dan Bergren, Eduard Eiben, Robert Ganian, and Iyad Kanj. On Covering Segments with Unit Intervals. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.STACS.2020.13

Abstract

We study the problem of covering a set of segments on a line with the minimum number of unit-length intervals, where an interval covers a segment if at least one of the two endpoints of the segment falls in the unit interval. We also study several variants of this problem.
We show that the restrictions of the aforementioned problems to the set of instances in which all the segments have the same length are NP-hard. This result implies several NP-hardness results in the literature for variants and generalizations of the problems under consideration.
We then study the parameterized complexity of the aforementioned problems. We provide tight results for most of them by showing that they are fixed-parameter tractable for the restrictions in which all the segments have the same length, and are W[1]-complete otherwise.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Computational geometry
Keywords
  • Segment covering
  • unit intervals
  • NP-completeness
  • parameterized complexity

Metrics

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

References

  1. A. Acharyya, S. Nandy, S. Pandit, and S. Roy. Covering segments with unit squares. Computational Geometry: Theory and Applications, 79:1-13, 2019. Google Scholar
  2. E. Arkin, A. Banik, P. Carmi, G. Citovsky, M. Katz, J. Mitchell, and M. Simakov. Choice is hard. In ISAAC, volume 9472 of Lecture Notes in Computer Science, pages 318-328. Springer, 2015. Google Scholar
  3. E. Arkin, A. Banik, P. Carmi, G. Citovsky, M. Katz, J. Mitchell, and M. Simakov. Conflict-free covering. In CCCG, 2015. Google Scholar
  4. E. Arkin, A. Banik, P. Carmi, G. Citovsky, M. Katz, J. Mitchell, and M. Simakov. Selecting and covering colored points. Discrete Applied Mathematics, 250:75-86, 2018. Google Scholar
  5. P. Bonsma, T. Epping, and W. Hochstättler. Complexity results on restricted instances of a paint shop problem for words. Discrete Applied Mathematics, 154(9):1335-1343, 2006. Google Scholar
  6. Y. Chen, J. Flum, and M. Grohe. Machine-based methods in parameterized complexity theory. Theoretical Computer Science, 339(2-3):167-199, 2005. Google Scholar
  7. M. Claverol, E. Khramtcova, E. Papadopoulou, M. Saumell, and C. Seara. Stabbing circles for sets of segments in the plane. Algorithmica, 80(3):849-884, 2018. Google Scholar
  8. T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 3rd edition, 2009. Google Scholar
  9. M. Cygan, F. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  10. R. Diestel. Graph Theory, 4th Edition. Springer, 2012. Google Scholar
  11. R. Downey and M. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin, Heidelberg, 2013. Google Scholar
  12. T. Erlebach and E. J. van Leeuwen. Approximating geometric coverage problems. In SODA, pages 1267-1276. SIAM, 2008. Google Scholar
  13. T. Erlebach and E.J. van Leeuwen. PTAS for weighted set cover on unit squares. In APPROX-RANDOM, volume 6302 of Lecture Notes in Computer Science, pages 166-177. Springer, 2010. Google Scholar
  14. M. R. Garey and D. S. Johnson. The rectilinear steiner tree problem in NP complete. SIAM Journal of Applied Mathematics, 32:826-834, 1977. Google Scholar
  15. A. Gupta, S. Kale, V. Nagarajan, R. Saket, and B. Schieber. The approximability of the binary paintshop problem. In APPROX-RANDOM, volume 8096 of Lecture Notes in Computer Science, pages 205-217. Springer, 2013. Google Scholar
  16. S. Hartung and R. Niedermeier. Incremental list coloring of graphs, parameterized by conservation. Theoretical Computer Science, 494:86-98, 2013. Google Scholar
  17. G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16(1):4-32, 1996. Google Scholar
  18. J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2005. Google Scholar
  19. K. Kobylkin. Stabbing line segments with disks: Complexity and approximation algorithms. In AIST, volume 10716 of Lecture Notes in Computer Science, pages 356-367. Springer, 2017. Google Scholar
  20. S. Langerman and P. Morin. Covering things with things. Discrete & Computational Geometry, 33(4):717-729, 2005. Google Scholar
  21. R. Madireddy and A. Mudgal. Stabbing line segments with disks and related problems. In CCCG, pages 201-207, 2016. Google Scholar
  22. J. Wang, W. Li, and J. Chen. A parameterized algorithm for the hyperplane-cover problem. Theoretical Computer Science, 411(44-46):4005-4009, 2010. Google Scholar
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact