Document Open Access Logo

Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs

Authors Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.65.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Fedor V. Fomin
Daniel Lokshtanov
Fahad Panolan
Saket Saurabh
Meirav Zehavi

Cite As Get BibTex

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 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 65:1-65:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.65

Abstract

We give algorithms with running time 2^{O({\sqrt{k}\log{k}})} n^{O(1)} for the following  problems. Given an n-vertex unit disk graph G and an integer k, decide whether G contains (i) a path on exactly/at least k vertices, (ii) a cycle on exactly k vertices, (iii) a cycle on at least k vertices, (iv) a feedback vertex set of size at most k, and (v) a set of k pairwise vertex disjoint cycles.  

For the first three problems, no subexponential time parameterized algorithms were previously known. For the remaining two problems, our algorithms significantly outperform the previously best known parameterized algorithms that run in time 2^{O(k^{0.75}\log{k})} n^{O(1)}. Our algorithms are based on a new kind of tree decompositions of unit disk graphs where the separators can have size up to k^{O(1)} and there exists a solution that crosses every separator at most O(\sqrt{k}) times. The running times of our algorithms are optimal up to the log{k} factor in the exponent, assuming the Exponential Time Hypothesis.

Subject Classification

Keywords
  • Longest Cycle
  • Cycle Packing
  • Feedback Vertex Set
  • Unit Disk Graph
  • Parameterized Complexity

Metrics

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

References

  1. Jochen Alber and Jiří Fiala. Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. In Foundations of Information Technology in the Era of Network and Mobile Computing, pages 26-37. Springer, 2002. Google Scholar
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. Assoc. Comput. Mach., 42(4):844-856, 1995. Google Scholar
  3. Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach., 41(1):153-180, 1994. Google Scholar
  4. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. CoRR, abs/1007.1161, 2010. Google Scholar
  5. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. Google Scholar
  6. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. URL: http://dx.doi.org/10.1016/j.jcss.2009.04.001.
  7. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^k n 5-approximation algorithm for treewidth. SIAM J. Comput., 45(2):317-378, 2016. URL: http://dx.doi.org/10.1137/130947374.
  8. Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms, 46(2):178-189, 2003. URL: http://dx.doi.org/10.1016/S0196-6774(02)00294-8.
  9. Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex cover: further observations and further improvements. Journal of Algorithms, 41(2):280-301, 2001. Google Scholar
  10. Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs. Discrete Mathematics, 86(1-3):165-177, 1990. Google Scholar
  11. Kenneth L. Clarkson and Kasturi R. Varadarajan. Improved approximation algorithms for geometric set cover. Discrete & Computational Geometry, 37(1):43-58, 2007. URL: http://dx.doi.org/10.1007/s00454-006-1273-8.
  12. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  13. Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. Journal of the ACM, 52(6):866-893, 2005. Google Scholar
  14. Erik D. Demaine and MohammadTaghi Hajiaghayi. Bidimensionality: new connections between FPT algorithms and PTASs. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 590-601, New York, 2005. ACM-SIAM. Google Scholar
  15. 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.
  16. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  17. 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.
  18. Adrian Dumitrescu and János Pach. Minimum clique partition in unit disk graphs. Graphs and Combinatorics, 27(3):399-411, 2011. Google Scholar
  19. Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. In Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), to appear, 2016. Google Scholar
  20. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM, 63(4):29, 2016. URL: http://dx.doi.org/10.1145/2886094.
  21. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs. ArXiv e-prints, April 2017. URL: https://arxiv.org/abs/1704.07279.
  22. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Bidimensionality and EPTAS. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 748-759, 2011. Google Scholar
  23. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Bidimensionality and geometric graphs. In SODA'12 Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms, pages 1563-1575. SIAM, 2012. Google Scholar
  24. F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Bidimensionality and kernels. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 503-510. SIAM, 2010. Google Scholar
  25. William K. Hale. Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12):1497-1514, 1980. Google Scholar
  26. Sariel Har-Peled and Mira Lee. Weighted geometric set cover problems revisited. JoCG, 3(1):65-85, 2012. Google Scholar
  27. Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294, pages 717-728. Springer, 2015. Google Scholar
  28. Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM, 32(1):130-136, 1985. Google Scholar
  29. Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi, Daniel J. Rosenkrantz, and Richard Edwin Stearns. NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms, 26(2):238-274, 1998. Google Scholar
  30. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity. Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  31. Hiro Ito and Masakazu Kadoshita. Tractability and intractability of problems on unit disk graphs parameterized by domain area. In Proceedings of the 9th International Symposium on Operations Research and Its Applications (ISORA10), pages 120-127, 2010. Google Scholar
  32. Bart M. P. Jansen. Polynomial kernels for hard problems on disk graphs. In Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 6139, pages 310-321. Springer, 2010. Google Scholar
  33. Karl Kammerlander. C 900 - An advanced mobile radio telephone system with optimum frequency utilization. IEEE journal on selected areas in communications, 2(4):589-597, 1984. Google Scholar
  34. Ioannis Koutis. Faster algebraic algorithms for path and packing problems. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), volume 5125 of Lecture Notes in Computer Science, pages 575-586, 2008. Google Scholar
  35. Ioannis Koutis and Ryan Williams. Algebraic fingerprints for faster algorithms. Commun. ACM, 59(1):98-105, 2016. URL: http://dx.doi.org/10.1145/2742544.
  36. Dániel Marx. Efficient approximation schemes for geometric problems? In Proceedings of the 13th Annual European Symposium on Algorithms (ESA), volume 3669, pages 448-459. Springer, 2005. Google Scholar
  37. Nabil H. Mustafa, Rajiv Raman, and Saurabh Ray. Settling the apx-hardness status for geometric set cover. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 541-550. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.64.
  38. Warren D. Smith and Nicholas C. Wormald. Geometric separator theorems & applications. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), pages 232-243. IEEE Computer Society, 1998. Google Scholar
  39. Stéphan Thomassé. A quadratic kernel for feedback vertex set. ACM Transactions on Algorithms, 6(2), 2010. Google Scholar
  40. DW Wang and Yue-Sun Kuo. A study on two geometric location problems. Information processing letters, 28(6):281-286, 1988. Google Scholar
  41. Ryan Williams. Finding paths of length k in O^*(2^k) time. Inf. Process. Lett., 109(6):315-318, 2009. Google Scholar
  42. Yu-Shuan Yeh, J. Wilson, and S. Schwartz. Outage probability in mobile telephony with directive antennas and macrodiversity. IEEE journal on selected areas in communications, 2(4):507-511, 1984. Google Scholar
  43. Meirav Zehavi. Mixing color coding-related techniques. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 1037-1049, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_86.
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