Document Open Access Logo

Feedback Vertex Set on Geometric Intersection Graphs

Authors Shinwoo An, Eunjin Oh

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.47.pdf
  • Filesize: 0.74 MB
  • 12 pages

Document Identifiers

Author Details

Shinwoo An
  • POSTECH, Pohang, South Korea
Eunjin Oh
  • POSTECH, Pohang, South Korea

Funding

This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No.2020R1C1C1012742).

Cite As Get BibTex

Shinwoo An and Eunjin Oh. Feedback Vertex Set on Geometric Intersection Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 47:1-47:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ISAAC.2021.47

Abstract

In this paper, we present an algorithm for computing a feedback vertex set of a unit disk graph of size k, if it exists, which runs in time 2^O(√k)(n+m), where n and m denote the numbers of vertices and edges, respectively. This improves the 2^O(√klog k) n^O(1)-time algorithm for this problem on unit disk graphs by Fomin et al. [ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time hypothesis. Also, our algorithm can be extended to handle geometric intersection graphs of similarly sized fat objects without increasing the running time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Feedback vertex set
  • intersection graphs
  • parameterized algorithm

Metrics

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

References

  1. Ann Becker and Dan Geiger. Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artificial Intelligence, 83(1):167-188, 1996. Google Scholar
  2. Sujoy Bhore, Paz Carmi, Sudeshna Kolay, and Meirav Zehavi. Parameterized study of Steiner tree on unit disk graphs. In Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), volume 162, pages 13:1-13:18, 2020. Google Scholar
  3. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Information and Computation, 243:86-111, 2015. 40th International Colloquium on Automata, Languages and Programming (ICALP 2013). Google Scholar
  4. Marthe Bonamy and Łukasz Kowalik. A 13k-kernel for planar feedback vertex set via region decomposition. Theoretical Computer Science, 645:25-40, 2016. Google Scholar
  5. Sergio Cabello and Miha Jejčič. Shortest paths in intersection graphs of unit disks. Computational Geometry, 48(4):360-367, 2015. Google Scholar
  6. Yixin Cao, Jianer Chen, and Yang Liu. On feedback vertex set: New measure and new structures. Algorithmica, 73(1):63-86, 2015. Google Scholar
  7. Timothy M Chan and Dimitrios Skrepetos. Approximate shortest paths and distance oracles in weighted unit-disk graphs. Journal of Computational Geometry, 10(2):3-20, 2019. Google Scholar
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer Publishing Company, Incorporated, 2015. Google Scholar
  9. Mark de Berg, Hans L Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C van der Zanden. A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs. SIAM Journal on Computing, 49(6):1291-1331, 2020. Google Scholar
  10. Erik D Demaine, Fedor V Fomin, Mohammadtaghi Hajiaghayi, and Dimitrios M Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and h-minor-free graphs. Journal of the ACM (JACM), 52(6):866-893, 2005. Google Scholar
  11. Hristo N Djidjev. Weighted graph separators and their applications. In Proceedings of the 5th Annual European Symposium on Algorithms (ESA 1997), pages 130-143. Springer, 1997. Google Scholar
  12. David P Dobkin, Steven J Friedman, and Kenneth J Supowit. Delaunay graphs are almost as good as complete graphs. Discrete & Computational Geometry, 5(4):399-407, 1990. Google Scholar
  13. Fedor V. Fomin, Serge Gaspers, and Artem V. Pyatkin. Finding a minimum feedback vertex set in time O (1.7548^n). In Hans L. Bodlaender and Michael A. Langston, editors, Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006), volume 4169, pages 184-191, 2006. Google Scholar
  14. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Finding, hitting and packing cycles in subexponential time on unit disk graphs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80, pages 65:1-65:15, 2017. Google Scholar
  15. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. ETH-tight algorithms for long path and cycle on unit disk graphs. In Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020), volume 164, pages 44:1-44:18, 2020. Google Scholar
  16. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Bidimensionality and geometric graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 1563-1575, 2012. Google Scholar
  17. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth. Routing in unit disk graphs. Algorithmica, 80(3):830-848, 2018. Google Scholar
  18. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Information Processing Letters, 114(10):556-560, 2014. Google Scholar
  19. Dániel Marx. Parameterized complexity of independence and domination on geometric graphs. In Proceedings of the 2nd International Conference on Parameterized and Exact Computation (IWPEC 2006), pages 154-165, 2006. Google Scholar
  20. Frank van den Eijkhof, Hans L Bodlaender, and MC Arie Koster. Safe reduction rules for weighted treewidth. Algorithmica, 47(2):139-158, 2007. 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